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

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

چگونگی عملکرد

آزمون کاسیسکی شرایط را برای تحلیل‌کنندهٔ رمز فراهم می‌کند تا او طول کلیدواژه مورد استفاده در رمزنگاری مبتنی بر جایگزینی چند الفبایی را بدست آورد. به محض اینکه طول کلید واژه کشف شود، تحلیلگر متن رمز شده را در 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. پس از پیدا کردن طول کلید، همانطور که در بالا مطرح شد در ادامه از تجزیه و تحلیل فرکانسی برای شکستن رمز استفاده می‌شود.

منابع
  1. http://en.wikipedia.org/wiki/Kasiski_examination
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.