چک جمع

از ویکیپدیا، دانشنامه آزاد
پرش به ناوبری پرش به جستجو
اثر یک تابع چک جمع معمولی ( cksumابزار Unix)

چک‌جمع بلوک کوچکی از داده‌ها است که از بلوک دیگری از داده‌های دیجیتال به‌منظور تشخیص خطاهایی که ممکن است در حین انتقال یا ذخیره‌سازی آن ایجاد شده باشد، به دست می‌آید . به خودی خود، جمع‌های کنترلی اغلب برای تأیید صحت داده‌ها استفاده می‌شوند، اما برای تأیید صحت داده‌ها به آنها اعتماد نمی‌شود .

رویه ای که این جمع چک را تولید می کند تابع چک جمع یا الگوریتم چک جمع نامیده می شود . بسته به اهداف طراحی خود، یک الگوریتم چک‌سوم خوب معمولاً مقدار متفاوتی را حتی برای تغییرات کوچکی که در ورودی ایجاد می‌شود، خروجی می‌دهد. این به ویژه در مورد توابع هش رمزنگاری صادق است ، که ممکن است برای شناسایی بسیاری از خطاهای خراب داده ها و تأیید یکپارچگی داده ها استفاده شود . اگر جمع کنترلی محاسبه شده برای ورودی داده فعلی با مقدار ذخیره شده یک جمع کنترلی محاسبه شده قبلی مطابقت داشته باشد، به احتمال بسیار زیاد داده ها به طور تصادفی تغییر نکرده یا خراب نشده اند.

توابع Checksum مربوط به توابع هش ، اثر انگشت ، توابع تصادفی سازی و توابع هش رمزنگاری هستند . با این حال، هر یک از آن مفاهیم کاربردهای متفاوتی دارند و بنابراین اهداف طراحی متفاوتی دارند. به عنوان مثال، تابعی که شروع یک رشته را برمی گرداند، می تواند یک هش مناسب برای برخی از برنامه ها ارائه کند، اما هرگز یک جمع کنترل مناسب نخواهد بود. چک‌سام‌ها به‌عنوان رمزنگاری اولیه در الگوریتم‌های احراز هویت بزرگ‌تر استفاده می‌شوند. برای سیستم های رمزنگاری با این دو هدف طراحی خاص، به HMAC مراجعه کنید .

ارقام چک و بیت های برابری موارد خاصی از جمع های چک هستند که برای بلوک های کوچک داده (مانند شماره های تامین اجتماعی، شماره حساب های بانکی ، کلمات کامپیوتری ، تک بایت ها و غیره) مناسب هستند. برخی از کدهای تصحیح خطا بر اساس جمع‌بندی‌های ویژه بررسی می‌شوند که نه تنها خطاهای رایج را شناسایی می‌کنند، بلکه اجازه می‌دهند داده‌های اصلی در موارد خاص بازیابی شوند.

الگوریتم ها

بایت برابری یا کلمه برابری

ساده ترین الگوریتم جمع کنترلی اصطلاحاً بررسی برابری طولی است که داده ها را با تعداد ثابت n بیت به "کلمات" تقسیم می کند و سپس انحصاری یا (XOR) همه آن کلمات را محاسبه می کند. نتیجه به عنوان یک کلمه اضافی به پیام اضافه می شود. برای بررسی یکپارچگی یک پیام، گیرنده انحصاری یا همه کلمات آن، از جمله چک جمع را محاسبه می کند. اگر نتیجه کلمه ای متشکل از n صفر نباشد، گیرنده می داند که یک خطای انتقال رخ داده است.

با استفاده از این جمع، هر خطای انتقالی که یک بیت از پیام یا تعداد عجیبی از بیت ها را برگرداند، به عنوان جمع کنترل نادرست شناسایی می شود. با این حال، خطایی که بر دو بیت تأثیر می گذارد، اگر آن بیت ها در دو کلمه مجزا در یک موقعیت قرار گیرند، شناسایی نمی شود. همچنین مبادله دو یا چند کلمه شناسایی نخواهد شد. اگر بیت‌های تحت تأثیر به‌طور مستقل به‌طور تصادفی انتخاب شوند، احتمال کشف نشدن خطای دو بیتی 1/ n است.

مکمل جمع

یک نوع از الگوریتم قبلی این است که همه "کلمات" را به عنوان اعداد باینری بدون علامت اضافه کنید، هر بیت سرریز را کنار بگذارید، و مکمل این دو را از کل به عنوان جمع کنترلی اضافه کنید. برای تأیید اعتبار یک پیام، گیرنده همه کلمات را به یک روش اضافه می کند، از جمله چک جمع. اگر نتیجه یک کلمه پر از صفر نباشد، باید خطایی رخ داده باشد. این نوع نیز هر گونه خطای تک بیتی را شناسایی می کند، اما مجموع مدولار حرفه ای در SAE J1708 استفاده می شود . [1]

وابسته به موقعیت

جمع‌های بررسی ساده که در بالا توضیح داده شد، قادر به تشخیص برخی از خطاهای رایج که روی بسیاری از بیت‌ها در یک زمان تأثیر می‌گذارند، مانند تغییر ترتیب کلمات داده، یا درج یا حذف کلمات با همه بیت‌ها روی صفر، نمی‌توانند. الگوریتم‌های جمع کنترلی که بیشتر در عمل مورد استفاده قرار می‌گیرند، مانند چک‌جمع فلچر ، آدلر-32 ، و چک‌های افزونگی چرخه‌ای (CRC)، نه تنها با در نظر گرفتن ارزش هر کلمه، بلکه همچنین موقعیت آن در دنباله، این نقاط ضعف را برطرف می‌کنند. این ویژگی به طور کلی هزینه محاسبه چک‌سوم را افزایش می‌دهد.

جمع کنترل فازی

ایده چک‌سوم فازی برای شناسایی هرزنامه‌های ایمیل با ایجاد پایگاه‌های داده مشترک از چندین ISP ایمیل مشکوک به اسپم توسعه داده شد. محتوای چنین هرزنامه‌هایی اغلب ممکن است در جزئیات آن متفاوت باشد، که جمع‌بندی چک عادی را بی‌اثر می‌کند. در مقابل، یک «جمع چک فازی» متن متن را به حداقل مشخصه‌اش کاهش می‌دهد، سپس یک جمع‌بندی بررسی را به روش معمول ایجاد می‌کند. این به میزان زیادی شانس ایمیل‌های هرزنامه متفاوتی را افزایش می‌دهد که چک‌سام یکسانی تولید کنند. نرم‌افزار شناسایی هرزنامه ISP، مانند SpamAssassin ، از ISPهای همکار، جمع‌بندی چک همه ایمیل‌ها را به سرویس متمرکز مانند DCC ارسال می‌کند.. اگر تعداد یک جمع‌بندی فازی ارسالی از یک آستانه خاص فراتر رود، پایگاه داده اشاره می‌کند که احتمالاً نشان دهنده هرزنامه است. کاربران سرویس ISP به طور مشابه یک چک‌سوم فازی در هر یک از ایمیل‌های خود ایجاد می‌کنند و از سرویس برای احتمال هرزنامه درخواست می‌کنند. [2]

ملاحظات کلی

پیامی که m بیت طول دارد را می توان به عنوان گوشه ای از ابر مکعب m بعدی مشاهده کرد. اثر یک الگوریتم جمع کنترلی که جمع کنترلی n بیتی را به دست می‌دهد این است که هر پیام m - bit را به گوشه‌ای از یک ابرمکعب بزرگتر با ابعاد m + n نگاشت می‌کند. گوشه های 2 m + n این ابر مکعب نشان دهنده همه پیام های دریافتی ممکن است. پیام‌های دریافتی معتبر (آنهایی که دارای جمع‌بندی صحیح هستند) مجموعه کوچک‌تری را تشکیل می‌دهند که تنها 2 متر گوشه دارد.

سپس یک خطای انتقال تک بیتی مربوط به جابجایی از یک گوشه معتبر (پیام صحیح و جمع بررسی) به یکی از m گوشه های مجاور است. خطایی که بر k بیت تأثیر می گذارد، پیام را به گوشه ای منتقل می کند که k قدم از گوشه صحیح آن حذف شده است. هدف یک الگوریتم چک‌سوم خوب این است که گوشه‌های معتبر را تا حد امکان از یکدیگر دور کند تا احتمال اینکه خطاهای انتقال «معمولی» به گوشه‌ای نامعتبر ختم شود، افزایش یابد.

همچنین مشاهده کنید

موضوع کلی

تصحیح خطا

توابع هش

سیستم های فایل

  • ZFS  - یک سیستم فایل که بررسی خودکار یکپارچگی فایل را با استفاده از چک‌سام انجام می‌دهد

مفاهیم مرتبط

منابع

  1. «SAE J1708» . Kvaser.com. بایگانی شده از نسخه اصلی در 11 دسامبر 2013.
  2. ^ "IXhash" . آپاچی بایگانی شده از نسخه اصلی در 31 اوت 2020 . بازیابی شده در 7 ژانویه 2020 .

پیوندهای خارجی