یك شنبه 11 خرداد 1399 |  عضویت / ورود

CheckSum چیست؟ (درباره الگوریتم کشف خطای مجموع مقابله‌ای)


Checksum یا «چکیده‌ی اعتبارسنجی» کاربرد زیادی دارد. مهم‌ترین کاربرد آن در بحث انتقال داده است. دانشجویان رشته کامپیوتر در درس شبکه با این مفهوم آشنا می‌شوند.

فرض کنید می‌خواهیم از طریق شبکه یک کاراکتر (یعنی ۷ بیت یا همان پالس برق) را بفرستیم. اگر در وسط مسیر به هر دلیلی (مثلاً به خاطر نویزی که کابل برق روی کابل شبکه ایجاد می‌کند و ده‌ها دلیل دیگر) یکی از بیت‌ها به جای اینکه مثلاً با قدرت ۱۰ ولت برسد که ما 0 در نظر بگیریم، با قدرت 50 ولت برسد و ما در مقصد آن‌را اشتباهاً 1 در نظر بگیریم، یک کاراکتر دیگر به مقصد خواهد رسید. (می‌دانید که در انتقال دیجیتال معمولاً دو نوع پالس برق می‌فرستند یکی نماد 0 و دیگری نماد 1. مثلاً یک پالس با ولتاژ 10 ولت و دیگری با ولتاژ 50 ولت است)

حالا چطور در مقصد بفهمیم که یکی از این بیت‌ها اشتباه رسیده و داده‌ی رسیده معتبر نیست؟

راه حل، استفاده از Checksum است. یعنی باید یک چکیده از کل داده‌ها به دست آوریم و همراه با داده‌ها ارسال کنیم که در مقصد با استفاده از آن چکیده بتوانیم اعتبارسنجی انجام دهیم.

ساده‌ترین نوع چک‌سام روشی به نام Parity bit (بیت توازن) است.

در این حالت، یک بیت به کل بیت‌ها اضافه می‌کنند که 0 یا 1 بودن آن‌ها به این صورت مشخص می‌شود: تعداد بیت‌های 1 را در داده می‌شمارند. اگر زوج بود، پریتی‌بیت را برابر 0 در نظر می‌گیرند و اگر فرد بود، 1 در نظر می‌گیرند.

مثلاً اگر قرار باشد ۷ بیت داده به صورت 1110111 را به مقصد بفرستیم، تعداد بیت‌های 1 را می‌شماریم، که اینجا 6 می‌شود، چون زوج است، پریتی‌بیت را 0 می‌کنیم. این بیت را به انتهای داده‌ها می‌چسبانیم و ارسال می‌کنیم. پس ۸ بیتِ ارسالی به این صورت خواهد شد: 11101110

حالا در مقصد هم ۷ بیت داده دریافت می‌شود و تعداد 1های آن شمرده می‌شود، سپس به پریتی‌بیت نگاه می‌شود. اگر تعداد 1ها زوج بود و پریتی‌بیت 0 بود، یعنی داده درست رسیده. اما اگر یکی از بیت‌های داده خراب شده باشد. مثلاً به جای یک، صفر ارسال شده باشد، می‌شود فهمید که داده خراب رسیده... (مثلاً اگر داده به شکل 10101110 رسیده باشد، تعداد 1ها فرد می‌شود در حالی که بیت توان 0 است و باید 1 می‌بود. این یعنی داده‌ها به هم ریخته) اگر داده خراب برسد، مقصد از مبدأ می‌خواهد که داده را دوباره بفرستد.

این روش هر چند ساده است اما در بسیاری از کارهای پیشرفته نیز از آن استفاده می‌شود. (مانند RAID-5 که یک رید جدید در ویندوز7 به بعد است: در این رِید، سه هارد دیسک به سیستم متصل می‌شود. یک بیت داده روی هارد اول درج می‌شود و بیت بعدی روی هارد دوم و بیت توازنِ آن‌دو روی هارد سوم... در این صورت هر کدام از این سه هارد که خراب شود، از روی دو هارد دیگر می‌توان اطلاعات هارد سوم را به دست آورد و با توجه به به‌کارگیری دو هد، سرعت خواندن و نوشتن هم دو برابر RAID-1 است)

روش‌های پیچیده‌تر Checksum:

ایده‌ی کلی در چک‌سام این است که یک خلاصه از کل داده‌ها به دست آید و همراه با داده ارسال شود. حالا این خلاصه ممکن است به روش‌های مختلف و کاملاً دلخواه ایجاد شود.

یکی از کاربردهای Cehcksum همان مفهوم Hash است که در مطلب «هش چیست؟» به آن اشاره کرده‌ام.

کاربرد دیگر آن در روش CRC استفاده می‌شود. در این روش، بیت‌هایی که قصد ارسال داریم، به یک عددِ توافقی در مبدأ و مقصد، تقسیم می‌کنیم و باقیمانده را به انتهای داده می‌چسبانیم و می‌فرستیم. در مقصد نیز بیت‌های رسیده را به همان عددِ توافقی تقسیم می‌کنیم اگر باقیمانده، همان باقیمانده‌ای شد که به انتهای داده چسبیده، یعنی داده درست رسیده اما اگر برابر نبود، یعنی یکی از بیت‌ها خراب رسیده...

 

برای اینکه درک بهتری از Checksum داشته باشید، دو مثال می‌زنم:

۱- بررسی صحت کد ملی:

فرض کنید نیروی انتظامی یک برنامه نوشته است برای اینکه مثلاً مشخصات یک دزد و دزدی‌اش را ثبت کند. شخصی که اطلاعات دزد را می‌پرسد، از دزد کد ملی‌اش را می‌پرسد. مثلاً کد ملی او 0123456789 است. حالا می‌خواهد در برنامه این کد را تایپ کند. به هر دلیلی، دستش اشتباهاً به جای 0 عدد 1 را تایپ می‌کند: 1123456789 !! می‌دانید چه می‌شود؟ دزدی به نام یک ایرانی دیگر ثبت می‌شود!!! و هزاران جای دیگر که این کد ملی کاربرد دارد نیز ممکن است بارها این اشتباهات سهوی رخ دهد!

برای جلوگیری از اشتباه در این انتقالِ کد از یک نفر به نفر دیگر، باز از Checksum استفاده می‌شود. رقم آخر کد ملی شما چک‌سام کد ملی‌تان است که به روش زیر به دست می‌آید:

فرض کنید می‌خواهیم رقم آخر کد ملی‌ای که نه رقم ابتدایی آن 093741103 است را به دست آوریم.

http://img.aftab.cc/news/93/iran_melli_code_algorithm.png

- از سمت چپ به هر کدام از ارقام کد ملی خودتان اعداد ۱۰ ، ۹ ، ۸ ،... تا ۲ را به عنوان ارزش آن ستون نسبت بدهید. (به جدول بالا نگاه کنید که بالای هر رقم از کد ملی، ارزش آن نوشته شده)
- هر رقمِ کد ملی را در ارزش ستونش ضرب کنید. (مثلاً رقم اول 0 است که در 10 ضرب می‌‌شود)
- نتیجه‌ی ضرب‌ها را با هم جمع کنید. (در مثال بالا عدد ۱۹۳ به دست می‌آید)
- باقیمانده‌ی تقسیم این عدد به ۱۱ را محاسبه کنید.
- عدد ۱۱ را منهای جواب کنید. (البته اگر باقیمانده‌ای که به دست آمد 0 یا 1 بود لازم نیست این مرحله را انجام دهید. همان باقیمانده، رقم آخر در نظر گرفته می‌شود)
- رقم آخر به دست می‌آید...

(روی کد ملی خودتان تست کنید! ببینید آیا رقم آخر کد ملی‌تان درست به دست می‌آید؟ نکند اشتباهی باشید!!؟)

خوب، با همین Checksum می‌شود صحت کد ملی‌ای که در برنامه‌ها وارد می‌شود را بررسی کرد. از روی نه رقم اول، رقم آخر به دست می‌آید، اگر آن رقم آخری که کاربر وارد کرده با چیزی که ما از طریق محاسبات به دست آورده‌ایم یکی بود، یعنی کد را درست وارد کرده وگرنه اشتباهی در تایپ کد ملی رخ داده.

۲- کد شابک کتاب‌ها:

این روزها کد شابک (مخفف: شماره استاندارد بین‌المللی کتاب و معادل ISBN: Internation Standard Book Number) یک کد ۱۳ رقمی است که مجدداً رقم آخر آن Checksum است و از روی ۱۲ رقم دیگر به صورت زیر به دست می‌آید:

http://img.aftab.cc/news/93/isbn_checksum.png

(یک کتاب بردارید و ببینید می‌توانید از روی ۱۲ رقم اول، رقم سیزدهم را به‌دست آورید؟)

در سریال نامبر برنامه‌ها هم از Checksum استفاده می‌شود:

شما قطعاً سریال‌نامبرهای برنامه‌های مختلف را دیده‌اید. مثلاً این یک سریال‌نامبر برای ویندوز 7 است: 342DG-6YJR8-X92GV-V7DCV-P4K27

این ارقام و حروف چطور به دست می‌آیند؟ هر کدام طبق یک فرمول بسیار پیچیده تولید می‌شوند. مثلاً شاید رقم اول آن، آخرین رقمِ تاریخ میلادی‌ای باشد که این کد تولید شده، مثلاً رقم دوم، از طریق سه برابر کردن رقم اول منهای ۵ به دست آمده باشد و از این جور فرمول‌ها... و احتمالاً رقم آخر، چک‌سام همه ارقام است که خودش ممکن است یک فرمول بسیار پیچیده داشته باشد. مثلاً رقم اول به توان رقم دوم، ضرب در رقم سوم به توان رقم چهارم، md5 این عدد را محاسبه کن و رقم آخر آن‌را به توان ۱۰ برسان و خلاصه آنقدر می‌پیچانند که به همین راحتی‌ها نشود آن‌را فهمید که کلید نامعتبر تولید کرد...

پس چطور برای برنامه‌ها KeyGen (مخفف Key Generator=تولیدکننده کلید) می‌سازند؟

خوب، کرَکِرها فقط کافی‌ست یک نسخه از برنامه را داشته باشند و یک کد جعلی به آن بدهد و سپس با ترفندهای مختلف، پردازش‌های CPU را زیر نظر بگیرند و ببینند CPU لحظه به لحظه دارد چه پردازشی روی این کد انجام می‌دهد تا آن‌را اعتبارسنجی کند؟ به همین سادگی (گاهی واقعاً ساده است) می‌فهمند که چه فرمول‌هایی روی کلید اعمال شد تا اعتبار سنجی شد. حالا همان فرمول‌ها را خیلی ساده به کی‌جن‌شان می‌دهند و شما با آن، کلیدهای جعلی می‌سازید که به راحتی از برنامه عبور کند...

 

به هر حال، ایده‌ی Checksum ایده‌ی بسیار مهمی است که اگر شما تولیدکننده نرم‌افزار باشید باید برای برنامه‌هایی که قصد فروش دارید، با فرمول‌هایی که خودتان با خودتان قرارداد می‌کنید، یک کلید تولید کنید و به مشتری بدهید. هنگام نصب از مشتری یک کلید می‌خواهید و سپس آن فرمول‌ها را روی آن کلید تست می‌کنید، اگر جواب همه فرمول‌ها با داده‌های کلید برابر بود، حالا اجازه استفاده از برنامه را می‌دهید...

موفق باشید؛
حمید رضا نیرومند


[ارسال شده در مورخه : چهارشنبه، 12 فروردین، 1394 توسط Hamid]
[ #دانستني‌هاي IT]

نظرات طرح شده

نام: [ کاربر جدید ]
ایمیل:

نظر:


اجازه استفاده از تگهای HTML را ندارید


جمع عدد 15 با 15 را در كادر زیر وارد نمایید:
(این كار برای جلوگیری از فعالیت موتورهای اسپمر است)


* توجه: نظر شما بعد از بررسی، نمایش داده خواهد شد.

[بدون موضوع]                توسط در مورخه : جمعه، 14 فروردین، 1394(لینک نظر)
حالا میفهمم چرا وقتی هزار بار کد شارژ ایرانسل امتحان میکردیم یکیش درس در نمیومد :D

و حالا میفهمم اونایی که میگفتن یبار الکی زدم 5تومن ، 2 تومن و ... شارژ شد احتمال بسیااار بالا خالی میبستن :D


[ ارسال جوابیه ]


آقا میلاد (امتیاز : 0)(لینک نظر)
توسط آقا میلاد در مورخه : شنبه، 15 فروردین، 1394
مهندس جان،

در مطلب بررسی صحت کد ملی،نتیجه 193 تقسیم بر یازده میشود 17.545454

که در شکل کلا غلط است.


[ ارسال جوابیه ]

    Hamid (امتیاز : 1)
    توسط Hamid در مورخه : شنبه، 15 فروردین، 1394
    سلام.

    آقا میلاد، باقیمانده رو حساب کن نه جواب تقسیم رو...


    [ ارسال جوابیه ]

      [بدون موضوع] (امتیاز : 0)
      توسط کاربر مهمان در مورخه : یکشنبه، 16 فروردین، 1394
      ممنون :-)


      [ ارسال جوابیه ]


احسان                توسط احسان در مورخه : جمعه، 9 بهمن، 1394(لینک نظر)
خیلی جالب بود ..


[ ارسال جوابیه ]


محمد احسان حیدری (امتیاز : 0)(لینک نظر)
توسط محمد احسان حیدری در مورخه : پنجشنبه، 5 فروردین، 1395
آقا من تست کردم کد ملیم درست بود :)

راستی میخوام یه وب سرویس بنویسم واسه تشخیص صحت کد ملی با WCF

ممنون میشم راهنماییم کنید


[ ارسال جوابیه ]


نرگس (امتیاز : 0)(لینک نظر)
توسط نرگس در مورخه : دوشنبه، 13 دی، 1395
مطلب ارائه شده در رابطه با checksum بسيار كاربردي بود .
متشكرم


[ ارسال جوابیه ]