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

در علم تحلیل رمز، آزمون کاسیسکی (یا تست کاسیسکی یا روش کاسیسکی) روشی برای حمله به رمزنگاری‌های مبتنی بر جایگزینی چند الفبایی، مانند رمزنگاری ویژنر است. این آزمون برای اولین بار توسط فردریش کاسیسکی در سال ۱۸۶۳ منتشر شد، اما به نظر می‌رسد قبل از آن به‌طور جداگانه توسط چارلز بابیج در سال ۱۸۴۶ کشف شده بوده.
چگونگی عملکرد
آزمون کاسیسکی شرایط را برای تحلیل‌کننده‌ی رمز فراهم می‌کند تا او طول کلیدواژه مورد استفاده در رمزنگاری مبتنی بر جایگزینی چند الفبایی را بدست آورد. به محض اینکه طول کلید واژه کشف شود، تحلیلگر متن رمز شده را در n ستون مرتب می‌کند که در آن n طول کلیدواژه است، سپس هر ستون را می‌توان به عنوان یک متن رمز شده‌ی مبتنی بر جایگزینی تک الفبایی مورد بررسی قرار داد. به این ترتیب، هر ستون را می‌توان با تحلیل فرکانسی مورد حمله قرار داد.
آزمون کاسیسکی شامل جست‌وجو برای یافتن رشته‌های کاراکتری تکرار شده در متن رمز شده می‌باشد. طول رشته‌های کاراکتری می‌بایست 3 کاراکتر یا بیشتر باشد تا آزمون کاسیسکی موفقیت‌آمیز باشد. سپس، فاصله میان رخدادهای متوالی از رشته‌ها به احتمال زیاد مضربی از طول کلیدواژه می‌باشد. بنابراین پیدا کردن رشته‌های تکراری بیشتر طول‌های ممکن برای کلیدواژه را محدود می‌کند، بدین ترتیب ما می‌توانیم بزرگترین مقسوم علیه مشترک تمام فاصله‌ها را بدست آوریم.
دلیل کارایی این آزمون این است که وقتی یک رشته به صورت مکرر در متنی رخ دهد، فاصله بین کاراکترهای تکراری مضربی از طول کلیدواژه می‌باشد. حروف کلید واژه به همان شیوه و با دو تکرار از رشته مرتب خواهند شد. به عنوان مثال، متن زیر را در نظر بگیرید:
crypto is short for cryptography.
" crypto " یک رشته‌ی تکراری است، و فاصله‌ی بین تکرارها 20 کاراکتر است. ما متن رمز نشده را ابتدا با کلیدواژه‌ی ۶ کاراکتری " abcdef " با توجه به اینکه ۲۰ بر ۶ بخش پذیر نیست و سپس با کلیدواژه‌ی 5 کاراکتری " abcde " با توجه به اینکه ۲۰ بر ۵ بخش پذیر است مرتب خواهیم کرد.
abcdef abcdefabcdefab cdefab cdefabc
crypto is short for crypto graphy
توجه کنید که اولین "crypto" مصادف با "abcdef" و تکرار دوم با "cdefab" می‌باشد، این دو نمونه به متون رمز شده‌ی مختلف رمزگذاری می‌شوند و آزمون کاسیسکی هیچ چیز را آشکار نخواهد ساخت.
abcdea bcdeabcdeabcde abcdea bcdeabc
crypto is short for crypto graphy
توجه کنید که هر دو تکرار رشته‌ی "crypto" مصادف با "abcdea" است. دو نمونه به یک متن رمز شده‌ی واحد تبدیل شدند در نتیجه آزمون کاسیسکی موثر خواهد بود.
یک حمله مبتنی بر رشته
سختی استفاده از آزمون کاسیسکی در پیدا کردن رشته‌های تکراری است. اگر این کار بخواهد به صورت دستی انجام شود بسیار مشکل است، اما رایانه‌ها می‌توانند این کار را بسیار آسان‌تر کنند. با این حال، هنوز دقت لازم است، به این خاطر که برخی از رشته‌های تکرار شده ممکن است تصادفی باشند، به این ترتیب برخی از فواصل تکرار گمراه‌کننده هستند. تحلیلگر میبایست بعضی از تکرارها را برای پیدا کردن طول درست کلیدواژه در نظر نگیرد. و البته در نهایت می‌بایست متن رمز شده‌ی بدست آمده از آزمون کاسیسکی که یک متن رمز شده‌ی تک الفبایی می‌باشد، مورد تحلیل قرار گیرد.
یک تحلیلگر رمز به دنبال گروه‌هایی از حروف‌های تکرار شده و تعداد حروف بین شروع هر گروه تکرار شده می‌باشد. برای مثال اگر متن رمز شده FGX THJAQWN FGX Q باشد، فاصله‌ی بین FGXها ۱۰ کاراکتر می‌باشد. تحلیلگر فواصل بین گروه‌های تکرار شده را ثبت می‌کند.
تحلیلگر در وهله بعد با داشتن هر یک از این اعداد کار را ادامه می‌دهد. اگر هر کدام از این شماره‌ها در اکثر این فاکتورها تکرار شده باشد، به احتمال زیاد آن عدد می‌تواند طول کلیدواژه باشد. دلیل این است که گروه‌های تکرار شده به احتمال زیاد هنگامی رخ می‌دهند که حروف رمزگذاری شده با استفاده کلیدهای یکسان رمزگذاری شده باشند تا با کلیدهای متفاوت، این امر به ویژه برای رشته‌های طولانی‌تر بیشتر صادق است. حروف کلید در مضاربی از طول کلید تکرار شده‌اند، بنابراین بسیاری از فاصله‌های یافت شده در مرحله‌ی اول به احتمال زیاد مضربی از طول کلید هستند. یک فاکتور مشترک معمولا آشکار است.
هنگامی که طول کلیدواژه مشخص شد، مشاهدات زیر از بابیج و کاسیسکی به کار می‌آیند. اگر طول کلیدواژه N حرف باشد، در نتیجه هر Nامین حرف باید با استفاده از حرف یکسانی از حروف کلید رمزگشایی شده باشد. در گروه بندی هر Nامین حرف با هم، تحلیلگر N متن به دست می‌آورد که هر متن با استفاده از یک رمزنگاری جایگزینی تک الفبایی رمز شده است، حال هر کدام از این متون بدست آمده را می‌توان به وسیله‌ی تحلیل فرکانسی مورد حمله قرار داد.
با استفاده از متن حل شده، تحلیلگر سریعتر می‌تواند متوجه شود که کلید چه بوده. یا، در روند حل قسمت‌های مسئله، تحلیلگر ممکن است از حدس زدن در مورد کلیدواژه برای کمک به شکستن این پیام استفاده کنید.
هنگامی که رهگیر کلیدواژه را می‌داند، این دانسته می‌تواند به خواندن پیام‌های دیگری که از همان کلید استفاده می‌کنند کمک کند.
آثار
کاسیسکی در واقع از "سوپرایمپوز" برای حل رمز ویژنر استفاده می‌کرد. همانطور که در بالا بیان شد او با پیدا کردن طول کلید شروع کرد. سپس او نسخه‌های متعدد از این پیام را گرفت آن‌ها را به یکی پس از دیگری روی هم گذاشته، سپس هر یک را به اندازه‌ی طول کلید به سمت چپ انتقال داد. کاسیسکی سپس مشاهده کرد که هر ستون از حروف رمزگذاری شده با یک الفبای واحد ساخته شده‌اند. روش او برابر با چیزی که در بالا توضیح داده شده بود، اما شاید در تصویر راحت‌تر باشد. حملات مدرن به رمزهای چند الفبایی، در اصل با چیزی که بالا توضیح داده شد یکسان هستند، البته با بهبود شمارش تصادفی. به جای دنبال گروه تکراری گشتن، یک تحلیلگر مدرن دو نسخه از پیام تهیه کرده آن‌ها را یکی بالاتر از دیگری قرار می‌دهد. تحلیلگران مدرن برای این کار از رایانه‌ها استفاده می‌کنند.
اما این توضیحات نشان دهنده‌ی این اصل است که می‌توان برای پیاده‌سازی الگوریتم‌ها از کامپیوتر کمک گرفت.
روش تعمیم
تحلیلگر ابتدا پیام پایینی را یک حرف به سمت چپ، و پس از آن دو حرف دیگر به سمت چپ، و به همین شکل ادامه می‌دهد. در هر بار چک کردن کل پیام و شمارش تعداد دفعات حرفی که در بالا و پایین پیام ظاهر می‌شود یکسانند.
تعداد انطباق‌ها هنگامی که پیام پایینی به اندازه‌ی مضربی از طول کلید شیفت پیدا می‌کند به شدت بالا می‌رود، و این مسئله به این دلیل است که حروف مجاور در زبانی یکسان از الفبای یکسان استفاده می‌کنند.
پس از پیدا کردن طول کلید، همانطور که در بالا مطرح شد در ادامه از تجزیه و تحلیل فرکانسی برای شکستن رمز استفاده می‌شود.