آزمون کاسیسکی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در علم تحلیل رمز، آزمون کاسیسکی[۱] (یا تست کاسیسکی یا روش کاسیسکی) روشی برای حمله به رمزنگاری های مبتنی بر جایگزینی چند الفبایی، مانند رمزنگاری ویژنر است. این آزمون برای اولین بار توسط فردریش کاسیسکی در سال ۱۸۶۳ منتشر شد، اما به نظر می رسد قبل از آن به طور جداگانه توسط چارلز بابیج در سال ۱۸۴۶ کشف شده بوده.

چگونگی عملکرد[ویرایش]

آزمون کاسیسکی شرایط را برای تحلیل کننده ی رمز فراهم می کند تا او طول کلیدواژه مورد استفاده در رمزنگاری مبتنی بر جایگزینی چند الفبایی را بدست آورد. به محض اینکه طول کلید واژه کشف شود، تحلیلگر متن رمز شده را در n ستون مرتب می کند که در آن n طول کلیدواژه است، سپس هر ستون را می توان به عنوان یک متن رمز شده ی مبتنی بر جایگزینی تک الفبایی مورد بررسی قرار داد. به این ترتیب، هر ستون را می توان با تحلیل فرکانسی مورد حمله قرار داد. آزمون کاسیسکی شامل جستوجو برای یافتن رشته های کاراکتری تکرار شده در متن رمز شده می باشد. طول رشته های کاراکتری می بایست 3 کاراکتر یا بیشتر باشد تا آزمون کاسیسکی موفقیت آمیز باشد. سپس، فاصله میان رخدادهای متوالی از رشته ها به احتمال زیاد مضربی از طول کلیدواژه می باشد. بنابراین پیدا کردن رشته های تکراری بیشتر طول های ممکن برای کلیدواژه را محدود می کند، بدین ترتیب ما می توانیم بزرگترین مقسوم علیه مشترک تمام فاصله ها را بدست آوریم. دلیل کارایی این آزمون این است که وقتی یک رشته به صورت مکرر در متنی رخ دهد، فاصله بین کاراکترهای تکراری مضربی از طول کلیدواژه می باشد. حروف کلید واژه به همان شیوه و با دو تکرار از رشته مرتب خواهند شد. به عنوان مثال، متن زیر را در نظر بگیرید:

crypto is short for cryptography.


"crypto" یک رشته ی تکراری است، و فاصله ی بین تکرارها 20 کاراکتر است. ما متن رمز نشده را ابتدا با کلیدواژه ی ۶ کاراکتری "abcdef" باتوجه به اینکه ۲۰ بر ۶ بخش پذیر نیست و سپس با کلیدواژه ی 5 کاراکتری "abcde" باتوجه به اینکه ۲۰ بر ۵ بخش پذیر است مرتب خواهیم کرد.

abcdefabcdefabcdefabcdefabcdefabc
crypto is short for cryptography

توجه کنید که اولین "crypto" مصادف با "abcdef" و تکرار دوم با "cdefab" می باشد، این دو نمونه به متون رمز شده ی مختلف رمزگذاری می شوند و آزمون کاسیسکی هیچ چیز را آشکار نخواهد ساخت.

abcdeabcdeabcdeabcdeabcdeabcdeabc
crypto is short for cryptography

توجه کنید که هر دو تکرار رشته ی "crypto" مصادف با "abcdea" است. دو نمونه به یک متن رمز شده ی واحد تبدیل شدند در نتیجه آزمون کاسیسکی موثر خواهد بود.

یک حمله مبتنی بر رشته[ویرایش]

سختی استفاده از آزمون کاسیسکی در پیدا کردن رشته های تکراری است. اگر این کار بخواهد به صورت دستی انجام شود بسیار مشکل است، اما رایانه ها می توانند این کار را بسیار آسان تر کنند. با این حال، هنوز دقت لازم است، به این خاطر که برخی از رشته های تکرار شده ممکن است تصادفی باشند، به این ترتیب برخی از فواصل تکرار گمراه کننده هستند. تحلیلگر میبایست بعضی از تکرارها را برای پیدا کردن طول درست کلیدواژه در نظر نگیرد. و البته در نهایت می بایست متن رمز شده ی بدست آمده از آزمون کاسیسکی که یک متن رمز شده ی تک الفبایی می باشد، مورد تحلیل قرار گیرد.

  1. یک تحلیلگر رمز به دنبال گروه هایی از حروف های تکرار شده و تعداد حروف بین شروع هر گروه تکرار شده می باشد. برای مثال اگر متن رمز شده FGXTHJAQWNFGXQ باشد، فاصله ی بین FGXها ۱۰ کاراکتر می باشد. تحلیلگر فواصل بین گروه های تکرار شده را ثبت می کند.
  2. تحلیلگر در وحله ی بعد با داشتن هر یک از این اعداد کار را ادامه می دهد. اگر هر کدام از این شماره ها در اکثر این فاکتورها تکرار شده باشد، به احتمال زیاد آن عدد می تواند طول کلیدواژه باشد. دلیل این است که گروه های تکرار شده به احتمال زیاد هنگامی رخ می دهند که حروف رمزگذاری شده با استفاده کلیدهای یکسان رمزگذاری شده باشند تا با کلیدهای متفاوت، این امر به ویژه برای رشته های طولانی تر بیشتر صادق است. حروف کلید در مضاربی از طول کلید تکرار شده اند، بنابراین بسیاری از فاصله های یافت شده در مرحله ی اول به احتمال زیاد مضربی از طول کلید هستند. یک فاکتور مشترک معمولا آشکار است.
  3. هنگامی که طول کلیدواژه مشخص شد، مشاهدات زیر از بابیج و کاسیسکی به کار می آیند. اگر طول کلیدواژه N حرف باشد، در نتیجه هر Nامین حرف باید با استفاده از حرف یکسانی از حروف کلید رمزگشایی شده باشد. در گروه بندی هر Nامین حرف با هم، تحلیلگر N متن به دست می آورد که هر متن با استفاده از یک رمزنگاری جایگزینی تک الفبایی رمز شده است، حال هر کدام از این متون بدست آمده را می توان به وسیله ی تحلیل فرکانسی مورد حمله قرار داد.
  4. با استفاده از متن حل شده، تحلیلگر سریعتر می تواند متوجه شود که کلید چه بوده. یا، در روند حل قسمت های مساله، تحلیلگر ممکن است از حدس زدن در مورد کلیدواژه برای کمک به شکستن این پیام استفاده کنید.
  5. هنگامی که رهگیر کلیدواژه را می داند، این دانسته می تواند به خواندن پیام های دیگری که از همان کلید استفاده می کنند کمک کند.

آثار[ویرایش]

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

روش تعمیم[ویرایش]

  1. تحلیلگر ابتدا پیام پایینی را یک حرف به سمت چپ، و پس از آن دو حرف دیگر به سمت چپ، و به همین شکل ادامه می دهد. در هر بار چک کردن کل پیام و شمارش تعداد دفعات حرفی که در بالا و پایین پیام ظاهر می شود یکسانند.
  2. تعداد انطباق ها هنگامی که پیام پایینی به اندازه ی مضربی از طول کلید شیفت پیدا می کند به شدت بالا می رود، و این مساله به این دلیل است که حروف مجاور در زبانی یکسان از الفبای یکسان استفاده می کنند.
  3. پس از پیدا کردن طول کلید، همانطور که در بالا مطرح شد در ادامه از تجزیه و تحلیل فرکانسی برای شکستن رمز استفاده می شود.

منابع[ویرایش]