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

در مبحث تحلیل رمز، تحلیل فراوانی  به مطالعهٔ تعداد دفعات تکرار یک حرف یا گروهی از حروف در یک متن رمزنگاری‌شده گفته می‌شود. از همین رو به تحلیل فراوانی، حروف‌شماری نیز می‌گویند. از این روش با هدفِ کمک به درهم شکستن روش‌های رمزنگاری کلاسیک استفاده می‌شود. این روش بر این پایه بنا شده است که در هر قطعه‌ای از یک زبان، هر حرفی (یا گروهی از حروف)، تعداد تکرار متفاوتی دارند. علاوه بر این، توزیع مشخصهٔ حروف الفبا تقریباً در تمام زبان‌ها یکسان است. برای مثال، در زبان انگلیسی، حروفِ , ,  و  بسیار رایج و پرتکرار هستند، و کاربردِ حروفِ ,  و  اندک است. به‌طور مشابه، , ,  و  پرتکرارترین جفت حروف (به آنها bigram یا digram نیز می‌گویند) هستند، و , ,  و  هم از نظر تعدادِ تکرارِ یک حرف خاص، رایج‌ترین جفت‌ها هستند. عبارت بی‌معنیِ ETAOIN SHRDLU نشان‌دهندهٔ ۱۲ حرف پرکاربرد در زبان انگلیسی عمومی است.

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

بندانگشتی|توزیع فراوانی حروف فارسی

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

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

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

 یک مثال 

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

 LIVITCSWPIYVEWHEVSRIQMXLEYVEOIEWHRXEXIPFEMVEWHKVSTYLXZIXLIKIIXPIJVSZEYPERRGERIM
 WQLMGLMXQERIWGPSRIHMXQEREKIETXMJTPRGEVEKEITREWHEXXLEXXMZITWAWSQWXSWEXTVEPMRXRSJ
 GSTVRIEYVIEXCVMUIMWERGMIWXMJMGCSMWXSJOMIQXLIVIQIVIXQSVSTWHKPEGARCSXRWIEVSWIIBXV
 IZMXFSJXLIKEGAEWHEPSWYSWIWIEVXLISXLIVXLIRGEPIRQIVIIBGIIHMWYPFLEVHEWHYPSRRFQMXLE
 PPXLIECCIEVEWGISJKTVWMRLIHYSPHXLIQIMYLXSJXLIMWRIGXQEROIVFVIZEVAEKPIEWHXEAMWYEPP
 XLMWYRMWXSGSWRMHIVEXMSWMGSTPHLEVHPFKPEZINTCMXIVJSVLMRSCMWMSWVIRCIGXMWYMX

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

Eve می‌تواند از تحلیل فراوانی استفاده کند تا در شکستن متن رمزشده به او کمک کند. تعداد حروف در متن رمزشده نشان می‌دهد که رایج‌ترین تک حرف است، رایج‌ترین bigram و رایج‌ترین trigram است. در زبان انگلیسیرایج‌ترین حرف، رایج‌ترین bigram و رایج‌ترین trigram است. این نتیجه‌گیری‌ها به شدت پیشنهاد می‌کنند که ~, ~ و ~ است. دومین حرف رایج در متن رمزشده،  است. از آنجایی که اولین و دومین حرف رایج در زبان انگلیسی  و  به حروف متناظر خود نسبت داده شدند پس Eve حدس می‌زند که ~ یعنی سومین حرف رایج باشد. به‌طور آزمایشی با انجام این فرضیات بخشی از پیام رمزگشایی می‌شود.


 heVeTCSWPeYVaWHaVSReQMthaYVaOeaWHRtatePFaMVaWHKVSTYhtZetheKeetPeJVSZaYPaRRGaReM
 WQhMGhMtQaReWGPSReHMtQaRaKeaTtMJTPRGaVaKaeTRaWHatthattMZeTWAWSQWtSWatTVaPMRtRSJ
 GSTVReaYVeatCVMUeMWaRGMeWtMJMGCSMWtSJOMeQtheVeQeVetQSVSTWHKPaGARCStRWeaVSWeeBtV
 eZMtFSJtheKaGAaWHaPSWYSWeWeaVtheStheVtheRGaPeRQeVeeBGeeHMWYPFhaVHaWHYPSRRFQMtha
 PPtheaCCeaVaWGeSJKTVWMRheHYSPHtheQeMYhtSJtheMWReGtQaROeVFVeZaVAaKPeaWHtaAMWYaPP
 thMWYRMWtSGSWRMHeVatMSWMGSTPHhaVHPFKPaZeNTCMteVJSVhMRSCMWMSWVeRCeGtMWYMt

با استفاده از این حدس‌های اولیه Eve الگوهایی که انتخاب‌هایش را تأیید می‌کند، استخراج کرده است مانند "". علاوه بر این، الگوهای دیگر حدس‌های دیگری را پیشنهاد می‌دهند. "" احتمالا "" است که یعنی ~. به طرز مشابهی "

" می‌تواند "" باشد که به معنی ~ و ~ است. "" احتمالا "" بوده است پس ~. با انجام این فرضیات، Eve به این متن رسید.

 hereTCSWPeYraWHarSseQithaYraOeaWHstatePFairaWHKrSTYhtmetheKeetPeJrSmaYPassGasei
 WQhiGhitQaseWGPSseHitQasaKeaTtiJTPsGaraKaeTsaWHatthattimeTWAWSQWtSWatTraPistsSJ
 GSTrseaYreatCriUeiWasGieWtiJiGCSiWtSJOieQthereQeretQSrSTWHKPaGAsCStsWearSWeeBtr
 emitFSJtheKaGAaWHaPSWYSWeWeartheStherthesGaPesQereeBGeeHiWYPFharHaWHYPSssFQitha
 PPtheaCCearaWGeSJKTrWisheHYSPHtheQeiYhtSJtheiWseGtQasOerFremarAaKPeaWHtaAiWYaPP
 thiWYsiWtSGSWsiHeratiSWiGSTPHharHPFKPameNTCiterJSrhisSCiWiSWresCeGtiWYit

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

 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 کرد یا آمارهای در دسترس را با عمق بیشتری نسبت به توجیهات ساده‌شدهٔ مثال بالا، بررسی کرد. همچنین ممکن است متن اصلی توزیع مورد انتظار فراوانی حروف را نداشته باشد. پیام‌های کوتاه‌تر تنوع بیشتری دارند. امکان ساختن متن‌های ساختگی نیز وجود دارد. برای مثال رمان‌هایی وجود دارند که به صورت کامل بدون استفاده از حرف  نوشته شده‌اند – یک نوع خاص از ادبیات به نام ستردگی.

 تاریخچه و کاربرد 


اولین توضیح ثبت شدهٔ مشخص از تحلیل فراوانی (در حقیقت هر نوعی از رمزنگاری) در قرن نهم توسط ابویوسف کندی، یک علامه عرب، در دست‌نوشته ایی در باب رمزگشایی پیام‌های رمزنگاری شده‌ ارائه شد.Ibrahim A. Al-Kadi "The origins of cryptology: The Arab contributions", Cryptologia, 16(2) (April 1992) pp. 97–126. به نظر می‌رسد که مطالعه دقیق متن قرآن برای اولین بار باعث روشن‌سازی این موضوع شده است که زبان عربی نیز دارای ویژگی فراوانی حروف است. استفاده از آن گسترش یافت و سیستم‌های مشابهی به‌طور گسترده در ایالت‌های اروپا در زمان رنسانس مورد استفاده قرار گرفت. در ۱۴۷۴ سیسو سیمونتا یک راهنما برای رمزگشایی متن‌های لاتین و ایتالیایی نوشت. تحلیل فراوانی عربی و همچنین مطالعه مفصل تحلیل فراوانی حروف و کلمات کل کتاب قرآن توسط مقاله Intellaren تهیه شده است.

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

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

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

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

 جستارهای وابسته 
 جستارهای رمزنگاری
 قانون زیف
 گدسبی (رمان) رمانی از Ernest Vincent Wright. این رمان به صورت ستردگی نوشته شده است و از کلماتی که حرف e داشته‌اند استفاده نشده است.

 منابع 

رده:توزیع فراوانی
رده:حمله‌های رمزنگاری

رده:اختراع‌های اعراب
رده:زبان‌شناسی کمی