تحلیل فراوانی

در مبحث تحلیل رمز، تحلیل فراوانی (به انگلیسی: frequency analysis) به مطالعهٔ تعداد دفعات تکرار یک حرف یا گروهی از حروف در یک متن رمزنگاری‌شده گفته می‌شود. از همین رو به تحلیل فراوانی، حروف‌شماری نیز می‌گویند. از این روش با هدفِ کمک به درهم شکستن روش‌های رمزنگاری کلاسیک استفاده می‌شود. این روش بر این پایه بنا شده‌است که در هر قطعه‌ای از یک زبان، هر حرفی (یا گروهی از حروف)، تعداد تکرار متفاوتی دارند. علاوه بر این، توزیع مشخصهٔ حروف الفبا تقریباً در تمام زبان‌ها یکسان است. برای مثال، در زبان انگلیسی، حروفِ E، T، A و O بسیار رایج و پرتکرار هستند، و کاربردِ حروفِ Z، Q و X اندک است. به‌طور مشابه، TH، ER، ON و AN پرتکرارترین جفت حروف (به آنها bigram یا digram نیز می‌گویند) هستند، و SS، EE، TT و FF هم از نظر تعدادِ تکرارِ یک حرف خاص، رایج‌ترین جفت‌ها هستند. عبارت بی‌معنیِ ETAOIN SHRDLU نشان‌دهندهٔ ۱۲ حرف پرکاربرد در زبان انگلیسی عمومی است.[1]

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

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

تحلیل فراوانی برای رمزنگاری جانشینی ساده

در یک رمزنگاری جانشینی ساده، هر حرف متن اصلی با یک حرف دیگر جایگزین می‌شود و هر حرف در متن اصلی همیشه به یک حرف مشخص در متن رمزشده تبدیل خواهد شد. برای مثال، اگر تمام رخدادهای حرف eبه حرف Xتبدیل شود، یک متن رمزشده شامل تعداد زیادی حرف Xخواهیم داشت و این به یک رمزنگار نشان خواهد داد که Xنمایانگر eاست.

استفاده‌ی ابتدایی از تحلیل فراوانی به این صورت است که فراوانی هر حرف متن رمزشده را حساب کنیم و سپس با توجه به آن، به صورت تخمینی حروف متن اصلی را به حروف متن رمز شده نسبت دهیم. هر چه تعداد Xدر متن رمزشده نسبت به باقی حروف بیشتر باشد به این معنی است که X احتمالا نمایانگر eدر متن اصلی است ولی این نتیجه گیری چندان هم قطعی نیست. tو aنیز حروف رایجی در زبان انگلیسی هستند پس Xمی‌تواند هرکدام از آنها باشد. این اتفاق برای حروف zو qکه کمتر رایج‌اند، بعید است اتفاق بیافتاد. بنابراین احتمالا رمزنگار باید چندین ترکیب از نگاشت حروف متن اصلی و رمزشده را بررسی کند.

کاربردهای پیچیده‌تر از کابردهای آماری را نیز می توان برای این تحلیل تصور کرد، مانند در نظر گرفتن تعداد جفت‌ها(bigrams)، سه تایی‌ها(trigrams) و غیره. این عمل برای تهیه اطلاعات بیشتر برای رمزنگار انجام می‌شود. برای مثال، Qو Uتقریبا همیشه با این ترتیب در زبان انگلیسی رخ می‌دهند حتی اگر خود Qبه تنهایی کمیاب باشد.

یک مثال

فرض کنید Eve، متن رمز‌شده زیر را یافته است و از قبل مشخص شده است که با استفاده از یک رمزنگاری جانشینی ساده به صورت زیر رمزگذاری شده است:

LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

برای این مثال، از حروف بزرگ برای نمایش متن رمزشده استفاده شده است، از حروف کوچک برای نمایش متن اصلی استفاده شده است و X~t برای نمایش یک حدس به کار میرود که در آن حرف متن رمزشده X نمایان‌گر حرف متن اصلی tاست.

Eve می‌تواند از تحلیل فراوانی استفاده کند تا در شکستن متن رمز‌شده به او کمک کند. تعداد حروف در متن رمز‌شده نشان می‌دهد که Iرایج‌ترین تک حرف است[2]، XLرایج‌ترین bigram و XLIرایج‌ترین trigram است. در زبان انگلیسیeرایج‌ترین حرف، thرایج‌ترین bigram و theرایج‌ترین trigram است. این نتیجه‌گیری‌ها به شدت پیشنهاد می‌کنند که X~t، L~h و I~e است. دومین حرف رایج در متن رمز‌شده، E است. از آنجایی که اولین و دومین حرف رایج در زبان انگلیسی e و t به حروف متناظر خود نسبت داده شدند پس Eve حدس می‌زند که E~a یعنی سومین حرف رایج باشد. به طور آزمایشی با انجام این فرضیات بخشی از پیام رمزگشایی می‌شود.

heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

با استفاده از این حدس‌های اولیه Eve‌ الگوهایی که انتخاب‌هایش را تایید می‌کند، استخراج کرده است مانند "that". علاوه بر این، الگوهای دیگر حدس‌های دیگری را پیشنهاد می‌دهند. "Rtate" احتمالا "state" است که یعنی R~s. به طرز مشابهی "atthattMZe" می‌تواند "atthattime" باشد که به معنی M~i و Z~m است. "heVe" احتمالا "here" بوده است پس V~r. با انجام این فرضیات، Eve به این متن رسید.

hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit}}

سپس این فرضیات حدس‌های دیگری را پیشنهاد می‌دهند(برای مثال "remarA" می‌تواند "remark" باشد یعنی A~k) و به همین ترتیب، استنباط حروف دیگر به صورت نسبی ساده است و در نهایت به متن اصلی زیر متنهی می‌شود.

hereuponlegrandarosewithagraveandstatelyairandbroughtmethebeetlefromaglasscasei
nwhichitwasencloseditwasabeautifulscarabaeusandatthattimeunknowntonaturalistsof
courseagreatprizeinascientificpointofviewthereweretworoundblackspotsnearoneextr
emityofthebackandalongoneneartheotherthescaleswereexceedinglyhardandglossywitha
lltheappearanceofburnishedgoldtheweightoftheinsectwasveryremarkableandtakingall
thingsintoconsiderationicouldhardlyblamejupiterforhisopinionrespectingit

در این مرحله لازم است تا Eve فاصله‌گذاری و نقطه‌گذاری‌ها را وارد کند:

Hereupon Legrand arose, with a grave and stately air, and brought me the beetle
from a glass case in which it was enclosed. It was a beautiful scarabaeus, and, at
that time, unknown to naturalists—of course a great prize in a scientific point
of view. There were two round black spots near one extremity of the back, and a
long one near the other. The scales were exceedingly hard and glossy, with all the
appearance of burnished gold. The weight of the insect was very remarkable, and,
taking all things into consideration, I could hardly blame Jupiter for his opinion
respecting it.

در این مثال از The Gold-Bug، تمام حدس‌های Eve درست بودند. همیشه اینطور نخواهد بود با این حال تغییر در آمارهای متن‌های اصلی منحصر بفرد می‌تواند به این معنا باشد که حدس‌های اولیه درست نیستند. شاید لازم باشد حدس‌های غلط را backtrack کرد یا آمارهای در دسترس را با عمق بیشتری نسبت به توجیهات ساده شده مثال بالا، بررسی کرد. همچنین ممکن است متن اصلی توزیع مورد انتظار فراوانی حروف را نداشته باشد. پیام‌های کوتاه‌تر تنوع بیشتری دارند. امکان ساختن متن‌های ساختگی نیز وجود دارد. برای مثال رمان‌هایی وجود دارند که به صورت کامل بدون استفاده از حرف e نوشته شده اند – یک نوع خاص از ادبیات به نام ستردگی.

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

اولین توضیح ثبت شده‌ی مشخص از تحلیل فراوانی(در حقیقت هر نوعی از رمزنگاری) در قرن نهم توسط ابویوسف کندی، یک علامه عرب، در دست‌نوشته ایی در باب رمزگشایی پیام‌های رمزنگاری شده‌ ارائه شد.[3] به نظر می‌رسد که مطالعه دقیق متن قرآن برای اولین بار باعث روشن‌سازی این موضوع شده است که زبان عربی نیز دارای ویژگی فراوانی حروف است.[4] استفاده از آن گسترش یافت و سیستم‌های مشابهی به طور گسترده در ایالت‌های اروپا در زمان رنسانس مورد استفاده قرار گرفت. در 1474 سیسو سیمونتا یک راهنما برای رمزگشایی متن‌های لاتین و ایتالیایی نوشت.[5] تحلیل فراوانی عربی و همچنین مطالعه مفصل تحلیل فراوانی حروف و کلمات کل کتاب قرآن توسط مقاله Intellaren تهیه شده است.[6]

چندین طرح توسط رمزنگاران برای غلبه بر ضعف‌های رمزنگاری جایگزینی ساده اختراع شده است. شامل:

  • جایگزینی هوموفونیک: استفاده از هوموفون‌ها – جایگزین‌های زیادی برای رایج‌ترین حروف در دیگر رمزنگاری‌های جانشینی تک‌حرفی. برای مثال برای زبان انگلیسی هم متن X و هم Y ممکن است معادل متن اصلی E باشند.
  • جایگزینی چند‌حرفی: کاربرد چندین حرف الفبا است – به شیوه‌های کمابیش منحرف متنوع، انتخاب شده است(به نظر می‌رسد لئون آلبرتی اولین کسی است که این موضوع را مطرح کرده است).
  • جایگزینی پلی­گرافیک: طرح‌هایی که جفت حرف‎ها یا سه‌گانه حرف‌های متن اصلی به عنوان واحدی برای جایگزینی به جای تک حرف‌ها استفاده می‌شوند. برای مثال رمزنگاری playfair که توسط چارلز ویتستون در اواسط قرن نوزدهم اختراع شد.

عیب همه این رویکردها در غلبه بر حمله‌های شمارش فراوانی، این است که باعث افزایش پیچیدگی رمزگشایی و رمزگذاری می‌شود که منجر به اشتباه می‌شود. گفته می‌شود یک دبیر خارجی بریتانیایی رمزنگاری playfair رد کرد به این علت که حتی اگر پسربچه‌های مدرسه‌ای هم بتوانند با موفقیت از عهده Wheatstone و Playfair برآیند، “کارکنان ما هرگز نمی توانند آن را یاد بگیرند”.

ماشین‌های گردان اوایل نیمه‌ی قرن بیستم(برای مثال ماشین انیگما) ضرورتا به تحلیل‌های فراوانی مستقیم ایمن بودند. با این حال دیگر نوع‌های تحلیل( "حمله ها") با موفقیت پیام‌ها را از برخی از آن ماشین‌ها رمزگشایی کردند.

تحلیل فراوانی فقط نیازمند یک درک ابتدایی از آمار زبان متن اصلی، برخی مهارت‌های حل مسئله و اگر به صورت دستی حل شود، توانایی برای سامان‌دهی حروف زیاد است. در طول جنگ جهانی دوم، بریتانیایی‌ها و آمریکایی‌ها با منتشر کردن جدول کلمات متقاطع در روزنامه‌ها و برگزاری مسابقات برای کسانی‌که بتوانند سریع‌تر از همه آنها را حل کنند،افرادی که رمزگشایی می‌کردند را استخدام کرده بودند. بسیاری از رمزهایی که توسط نیروهای محور استفاده می‌شدند با استفاده از تحلیل فراوانی قابل رمزگشایی بودند. برای مثال رمزهای کنسولگری مورد استفاده ژاپنی‌ها. روش‌های مکانیکی شمارش حروف و تحلیل آماری(عمدتا ماشین‌های با نوع کارت IBM) اولین بار در جنگ جهانی دوم احتمالا توسط ارتش SIS آمریکا استفاده شدند. امروزه کار سخت شمارش و تحلیل حروف با نرم‌افزار‌های کامپیوتری جایگزین شده‌اند که قابلیت تحلیل در عرض چند ثانیه را دارند. با قدرت محاسبه مدرن، بعید است که رمزهای کلاسیک بتوانند به صورت واقعی از داده‌های محرمانه محافظت کنند.

تحلیل فراوانی در داستان‌ها
فراوانی حروف در اسپانایی

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

جستارهای وابسته

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Frequency analysis». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۲۲ می ۲۰۲۰.

  1. Singh, Simon. "The Black Chamber: Hints and Tips". Retrieved 26 October 2010.
  2. "A worked example of the method from bill's "A security site.com"". Archived from the original on 2013-10-20. Retrieved 2012-12-31.
  3. Ibrahim A. Al-Kadi "The origins of cryptology: The Arab contributions", Cryptologia, 16(2) (April 1992) pp. 97–126.
  4. "In Our Time: Cryptography". BBC Radio 4. Retrieved 29 April 2012.
  5. Kahn, David L. (1996). The codebreakers: the story of secret writing. New York: Scribner. ISBN 0-684-83130-9.
  6. Madi, Mohsen M. (2010). "Quran Suras Statistics". Intellaren Articles. Retrieved 16 January 2011.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.