مؤشر التزامن

في علم التشفير ، يُعرف عدّ التطابقات بأنه أسلوب (ابتكره ويليام ف. فريدمان ^{[ 1 ]} ) يقوم على وضع نصين جنبًا إلى جنب وحساب عدد مرات ظهور الأحرف المتطابقة في الموضع نفسه في كلا النصين. يُعرف هذا العدد، سواء كنسبة من الإجمالي أو مُقسّمًا على العدد المتوقع لنموذج مصدر عشوائي، باسم مؤشر التطابق ، أو اختصارًا IC أو IOC ^{[ 2 ]} أو IoC ^{[ 3 ]} .

لأن الأحرف في اللغة الطبيعية لا تتوزع بالتساوي ، فإن قيمة IC تكون أعلى في هذه النصوص مقارنةً بسلاسل النصوص العشوائية المنتظمة. وتكمن أهمية IC في أن قيمتها لا تتغير إذا تم تشفير كلا النصين باستخدام نفس خوارزمية استبدال الأحرف ، مما يسمح لمحلل التشفير باكتشاف هذا النوع من التشفير بسرعة.

يُقدّم مؤشر التطابق مقياسًا لاحتمالية سحب حرفين متطابقين عن طريق اختيار حرفين عشوائيًا من نص مُعطى. احتمال سحب حرف مُعين في النص هو (عدد مرات ظهور هذا الحرف / طول النص). احتمال سحب نفس الحرف مرة أخرى (بدون إرجاع) هو (عدد مرات الظهور - 1 / طول النص - 1). حاصل ضرب هاتين القيمتين يُعطي احتمال سحب هذا الحرف مرتين متتاليتين. يُمكن حساب هذا الناتج لكل حرف يظهر في النص، ثم جمع هذه النواتج للحصول على احتمال سحب حرفين متطابقين. يُمكن بعد ذلك توحيد هذا الاحتمال بضربه في مُعامل مُعين، عادةً 26 في اللغة الإنجليزية.

${\displaystyle \mathbf {IC} =c\times \left({\left({{\frac {n_{\mathrm {a} }}{N}}\times {\frac {n_{\mathrm {a} }-1}{N-1}}}\right)+\left({{\frac {n_{\mathrm {b} }}{N}}\times {\frac {n_{\mathrm {b} }-1}{N-1}}}\right)+\cdots +\left({{\frac {n_{\mathrm {z} }}{N}}\times {\frac {n_{\mathrm {z} }-1}{N-1}}}\right)}\right)}$

حيث c هو معامل التطبيع (26 للغة الإنجليزية)، و n _a هو عدد مرات ظهور الحرف "a" في النص، و N هو طول النص.

يمكننا التعبير عن مؤشر التطابق IC لتوزيع تردد الأحرف المعطاة كمجموع:

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{i=1}^{c}n_{i}(n_{i}-1)}{N(N-1)/c}}}$

حيث N هو طول النص، و _{n1 إلى nc هي} ترددات ( كأعداد صحيحة ) حروف الأبجدية c ( c = 26 للغة الإنجليزية أحادية الحالة ) . مجموع n1 هو بالضرورة _N.

تحسب حاصل ضرب n ( n -1) عدد التوليفات الممكنة لـ n عنصرًا، كل عنصرين على حدة. (في الواقع، يُحسب كل زوج مرتين؛ إذ يظهر العامل 2 في كل من بسط ومقام الصيغة، وبالتالي يُلغى). كل ظهور من بين n  i  للحرف i يتطابق مع كل ظهور متبقٍ من بين n i -1 لنفس الحرف. يوجد إجمالي N ( N -1) زوجًا من الأحرف في النص بأكمله، و1/ c هو احتمال التطابق لكل زوج، بافتراض توزيع عشوائي منتظم للأحرف (النموذج الصفري؛ انظر أدناه). بالتالي، تُعطي هذه الصيغة نسبة إجمالي عدد حالات التطابق الملاحظة إلى إجمالي عدد حالات التطابق المتوقعة من النموذج الصفري. [ 4 ]

يمكن حساب القيمة المتوسطة المتوقعة لـ IC من الترددات النسبية للأحرف f _i للغة المصدر:

${\displaystyle \mathbf {IC} _{\mathrm {expected} }={\frac {\displaystyle \sum _{i=1}^{c}{f_{i}}^{2}}{1/c}}.}$

إذا كانت جميع حروف الأبجدية ذات احتمالية متساوية، فسيكون المؤشر المتوقع 1.0. أما مؤشر IC الأحادي الفعلي للنص الإنجليزي التلغرافي فهو حوالي 1.73، مما يعكس عدم انتظام توزيع حروف اللغة الطبيعية .

أحيانًا تُذكر القيم دون المقام المعياري، على سبيل المثال 0.067 = 1.73/26 للغة الإنجليزية؛ وقد تُسمى هذه القيم κ _p ("نص كابا عادي") بدلًا من IC، حيث يُستخدم κ _r ("كابا عشوائي") للدلالة على المقام 1/ c (وهو معدل التطابق المتوقع لتوزيع منتظم لنفس الأبجدية، 0.0385 = 1/26 للغة الإنجليزية). يقع النص الإنجليزي العادي عمومًا في نطاق يتراوح بين 1.5 و2.0 (حساب معياري). ^{[ 5 ]}

يُعدّ مؤشر التطابق مفيدًا في تحليل النصوص الأصلية المكتوبة بلغة طبيعية، وكذلك في تحليل النصوص المشفرة ( التحليل التشفيري ). حتى عند توفر النص المشفر فقط للاختبار، وإخفاء هوية حروف النص الأصلي، قد ينتج التطابق في النص المشفر عن تطابق في النص الأصلي. تُستخدم هذه التقنية ، على سبيل المثال، في تحليل تشفير فيجنير . بالنسبة لتشفير متعدد الأبجديات ذي مفتاح متكرر مُرتب في مصفوفة، يكون معدل التطابق داخل كل عمود عادةً في أعلى مستوياته عندما يكون عرض المصفوفة من مضاعفات طول المفتاح، ويمكن استخدام هذه الحقيقة لتحديد طول المفتاح، وهي الخطوة الأولى في فك التشفير.

يمكن أن يساعد حساب التطابقات في تحديد متى كُتب نصان بنفس اللغة وبنفس الأبجدية . (استُخدمت هذه التقنية لدراسة ما يُزعم أنه شفرة الكتاب المقدس ). سيكون عدد التطابقات السببية لمثل هذه النصوص أعلى بكثير من عدد التطابقات العرضية للنصوص المكتوبة بلغات مختلفة، أو النصوص التي تستخدم أبجديات مختلفة، أو النصوص غير المفهومة.

لفهم السبب، تخيل "أبجدية" تتكون من الحرفين A وB فقط. لنفترض أن الحرف A يُستخدم في "لغتنا" بنسبة 75%، بينما يُستخدم الحرف B بنسبة 25%. إذا وُضِع نصان مكتوبان بهذه اللغة جنبًا إلى جنب، فمن المتوقع ظهور الأزواج التالية:

بشكل عام، فإن احتمال "الصدفة" هو 62.5٪ (56.25٪ لـ AA + 6.25٪ لـ BB).

والآن، لنفترض الحالة التي يتم فيها تشفير كلتا الرسالتين باستخدام تشفير الاستبدال الأحادي الأبجدي البسيط الذي يستبدل الحرف A بالحرف B والعكس صحيح:

تبلغ احتمالية التطابق الإجمالية في هذه الحالة 62.5% (6.25% لـ AA + 56.25% لـ BB)، وهي النسبة نفسها تمامًا كما في حالة النص الأصلي غير المشفر. في الواقع، الأبجدية الجديدة الناتجة عن الاستبدال ليست سوى إعادة تسمية موحدة لهويات الأحرف الأصلية، ولا يؤثر ذلك على تطابقها.

لنفترض الآن أنه تم تشفير رسالة واحدة فقط (لنقل الثانية) باستخدام نفس خوارزمية التشفير بالاستبدال (A,B)→(B,A). يمكن توقع الأزواج التالية:

الآن، تبلغ احتمالية المصادفة 37.5% فقط (18.75% للحرفين AA و18.75% للحرفين BB). وهذا أقل بكثير من الاحتمالية عند استخدام نصوص من نفس اللغة والأبجدية. من الواضح أن المصادفات تزداد احتماليةً عندما تكون الأحرف الأكثر تكرارًا في كل نص هي نفسها.

The same principle applies to real languages like English, because certain letters, like E, occur much more frequently than other letters—a fact which is used in frequency analysis of substitution ciphers. Coincidences involving the letter E, for example, are relatively likely. So when any two English texts are compared, the coincidence count will be higher than when an English text and a foreign-language text are used.

This effect can be subtle. For example, similar languages will have a higher coincidence count than dissimilar languages. Also, it is not hard to generate random text with a frequency distribution similar to real text, artificially raising the coincidence count. Nevertheless, this technique can be used effectively to identify when two texts are likely to contain meaningful information in the same language using the same alphabet, to discover periods for repeating keys, and to uncover many other kinds of nonrandom phenomena within or among ciphertexts.

Expected values for various languages^[6] are:

The above description is only an introduction to use of the index of coincidence, which is related to the general concept of correlation. Various forms of Index of Coincidence have been devised; the "delta" I.C. (given by the formula above) in effect measures the autocorrelation of a single distribution, whereas a "kappa" I.C. is used when matching two text strings.^[7] Although in some applications constant factors such as ${\displaystyle c}$ and ${\displaystyle N}$ can be ignored, in more general situations there is considerable value in truly indexing each I.C. against the value to be expected for the null hypothesis (usually: no match and a uniform random symbol distribution), so that in every situation the expected value for no correlation is 1.0. Thus, any form of I.C. can be expressed as the ratio of the number of coincidences actually observed to the number of coincidences expected (according to the null model), using the particular test setup.

From the foregoing, it is easy to see that the formula for kappa I.C. is

${\displaystyle \mathbf {IC} ={\frac {\displaystyle \sum _{j=1}^{N[a_{j}=b_{j}]}{N/c}},}$

where ${\displaystyle N}$ is the common aligned length of the two texts A and B, and the bracketed term is defined as 1 if the ${\displaystyle j}$-th letter of text A matches the ${\displaystyle j}$-th letter of text B, otherwise 0.

يقيس مفهوم ذو صلة، وهو "انتفاخ" التوزيع، التباين بين قيمة IC المرصودة والقيمة الصفرية 1.0. ويمكن تقدير عدد أبجديات التشفير المستخدمة في التشفير متعدد الأبجديات بقسمة الانتفاخ المتوقع لقيمة دلتا IC لحرف أبجدي واحد على الانتفاخ المرصود للرسالة، على الرغم من وجود تقنيات أفضل في كثير من الحالات (مثل استخدام مفتاح متكرر ).

كمثال عملي على استخدام تقنية التشفير المتكامل، لنفترض أننا اعترضنا رسالة النص المشفر التالية:

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDHXC XJYEB IMTRQ WNMEA IZRVK CVKVL XNEIC FZPZC ZZHKM LVZVZ IZRRQ WDKEC HOSNY XXLSP MYKVQ XJTDC IOMEE XDQVS RXLRL KZHOV

(إن تجميع الأحرف في خمسة أحرف هو مجرد اصطلاح تلغرافي ولا علاقة له بأطوال الكلمات الفعلية.) بافتراض أن هذا نص إنجليزي عادي مشفر باستخدام شيفرة فيجنير مع مكونات A-Z عادية وكلمة مفتاحية قصيرة متكررة، يمكننا اعتبار النص المشفر "مكدسًا" في عدد من الأعمدة، على سبيل المثال سبعة:

QPWKALV RXCQZIK GRBPFAE OMFLJMS DZVDHXC XJYEBIM TRQWN… 

إذا كان حجم المفتاح مساويًا لعدد الأعمدة المفترض، فسيتم تشفير جميع الأحرف داخل عمود واحد باستخدام نفس حرف المفتاح، أي تطبيق بسيط لخوارزمية قيصر على مجموعة عشوائية من أحرف النص الإنجليزي. يجب أن يكون لتوزيع تردد الأحرف المشفرة تقريب مشابه لتوزيع تردد الأحرف الإنجليزية، على الرغم من تبديل هويات الأحرف (إزاحتها بمقدار ثابت يتوافق مع حرف المفتاح). لذلك، إذا حسبنا إجمالي دلتا IC لجميع الأعمدة ("دلتا بار")، فسيكون حوالي 1.73. من ناحية أخرى، إذا أخطأنا في تقدير حجم المفتاح (عدد الأعمدة)، فسيكون إجمالي دلتا IC حوالي 1.00. لذا، نحسب دلتا IC لأحجام مفاتيح مفترضة من واحد إلى عشرة.

نلاحظ أن حجم المفتاح على الأرجح هو خمسة. إذا كان الحجم الفعلي خمسة، فمن المتوقع أن يُظهر عرض عشرة أيضًا قيمة عالية لـ IC، لأن كل عمود من أعمدته يتوافق مع تشفير قيصر بسيط، وقد تأكدنا من ذلك. لذا، ينبغي لنا تكديس النص المشفر في خمسة أعمدة.

QPWKA LVRXC QZIKG RBPFA EOMFL JMSDZ VDH… 

We can now try to determine the most likely key letter for each column considered separately, by performing trial Caesar decryption of the entire column for each of the 26 possibilities A–Z for the key letter, and choosing the key letter that produces the highest correlation between the decrypted column letter frequencies and the relative letter frequencies for normal English text. That correlation, which we don't need to worry about normalizing, can be readily computed as

${\displaystyle \mathbf {\chi } =\sum _{i=1}^{c}n_{i}f_{i}}$

where ${\displaystyle n_{i}}$ are the observed column letter frequencies and ${\displaystyle f_{i}}$ are the relative letter frequencies for English. When we try this, the best-fit key letters are reported to be "EVERY," which we recognize as an actual word, and using that for Vigenère decryption produces the plaintext:

MUSTC HANGE MEETI NGLOC ATION FROMB RIDGE TOUND ERPAS SSINC EENEM YAGEN TSARE BELIE VEDTO HAVEB EENAS SIGNE DTOWA TCHBR IDGES TOPME ETING TIMEU NCHAN GEDXX 

from which one obtains:

MUST CHANGE MEETING LOCATION FROM BRIDGE TO UNDERPASS SINCE ENEMY AGENTS ARE BELIEVED TO HAVE BEEN ASSIGNED TO WATCH BRIDGE STOP MEETING TIME UNCHANGED XX 

after word divisions have been restored at the obvious positions. "XX" are evidently "null" characters used to pad out the final group for transmission.

This entire procedure could easily be packaged into an automated algorithm for breaking such ciphers. Due to normal statistical fluctuation, such an algorithm will occasionally make wrong choices, especially when analyzing short ciphertext messages.

• Kasiski examination
• Riverbank Publications
• Topics in cryptography