Solving monoalphabetic substitution ciphers

[dj-siba]

المشاركة الأصلية كتبت بواسطة Mr Paradox في 12-01-2016 الساعة 01:15 AM:

شفرات MONOALPHABETIC SUBSTITUTION CIPHER

مقدمة :
هذا النوع يعتبر من أقدم أنواع التشفير استخداما، حيث نقوم في هذا النوع بإحلال substitution حرف من النص الأصلي بحرف آخر جديد وهو بالإضافة إلى قدمه يعتبر من أضعف أنواع التشفير ويسهل كسره بطريقة تسمى التحليل الإحصائي Frequency Analysis وهذه الطريقة من اكتشاف العالم المسلم أبو يعقوب الكندي وهو أول من وضع أساسيات كسر الشفرات Cryptanalysis، حيث لاحظ حروف تتكرر في القرآن الكريم أكثر من غيرها.
من أشهر شفرات هذا النوع: Monoalphabetic Substitution
1- Caesar Cipher
2- Affine Cipher
3- Abash Cipher

مثال دراستنا اليوم سيهم تشفير القيصر Caesar Cipher
1-آلية العمل:

تقوم على إزاحة كل حرف من النص الأصلي بعدد ثابت من مواقع الأحرف بالأبجدية Shift Cipher

Definition  Shift Cipher
Let X, Y, K€Z26
Encryption  :  Ek (x) = (x + k) mod 26
Decryption  :  Dk (y) = (y - k) mod 26

حيث يرمز للأحرف بأرقام كما بالشكل :



نلاحظ أن المفتاح (قيمة الإزاحة) يوجد بين (0 و 25) لأنه أذا كان أكثر من ذلك فلن يكون له معنى مثلا 27 إزاحة تساوي إزاحة واحدة حسب الشكل السابق أذا عدد احتمالات المفتاح 26 احتمال.
مثال:
ARABTEAMFORREVERSEENGINEERING
باستخدم المفتاح 5 نحصل على :
FWFGYJFRKTWWJAJWXJJSLNSJJWNSL

ملاحظة هامة:
عند التشفير إزالة كل الفراغات من النص المشفر لأن ترتيب الحروف في النص الأصلي يسهل من عملية تخمين الكلمة وعدم ترك  أي حرف منعزل مثال :
Ghflskhulqj lv grqh lq uhyhuvh, zlwk d uljkw vkliw ri 3.
إذا علمنا أن لغة النص الأصلية إنجليزية فالحرف D المنعزل لايمكن أن يكون إلا أحد الحرفينA أو I وبالتالي يمكن استخلاص المفتاح.


2-كسر شيفرة قيصر عن طريق  Brute - Force Attack
كما لاحظنا بشفرة قيصر عدد احتمالات المفاتيح قليل جدا 25، لذا يمكن تجربة جميع الاحتمالات 1..25 فهذا الهجوم عمليا ممكن عليها سواء برمجيا أو يدويا.
ممكن الإطلاع على حل الأخ naquardia بالتمرين 1-DecodeMe

3-كسر شيفرة قيصر عن طريق Frequency Analysis
جميع اللغات سواء عربية أم إنجليزية أم لغات أخرى تحتوي على حروف تتكرر دائما وباستمرار في الجمل، في اللغة العربية مثلا نجد ا، ل ..، أما في اللغة الإنجليزية فالحرف E الأكثر تكرارا في الجمل.
إذا علمنا أن تشفيرات Monoalphabetic Substitution تحفظ التردد الإحصائي للحروف ومؤشر المصادفة Index of coincidence لكل لغة، فطريقة التحليل الإحصائي تعتمد على هذا الإحتمال فنحصي الحروف في النص المشفر وننظر للحرف الأكثر ترددا الذي يقابله الحرف E في اللغة الإنجليزية.
ملاحظة مهمة : Index of Coincidence يمكننا من معرفة لغة النص النص الأصلية كما أنه يمكننا من تمييز إن كان نوع التشفير Monoalphabetic Substitution أم Polyalphabetic Substitution أو شيء آخر. ( لن أكثر في هذا الباب وسأتركه للدروس القادمة )



طبعا الإحتمال في بعض الأحيان لايكون صحيحا لاكن يصلح في تشفيرة قيصر وخصوصا النصوص الطويلة.

مثال النص المشفر الآتي (رغم أن النص قصير لاكنه للتوضيح لا غير):
FWFGYJFRKTWWJAJWXJJSLNSJJWNSL

A: 1 - B: 0 - C: 0 - D: 0 - E: 0 - F: 3 - G: 1 - H: 0 -  I:  0 - J: 7 - K: 1 - L: 2 - M: 0
N: 2 - O: 0 - P: 0 - Q: 0 - R: 1 - S: 3 - T: 1 - U: 0 - V: 0 - W: 5 - X: 1 - Y: 1 - Z: 0
إذن E تقابل الحرف J ومنه نستنتج مفتاح التشفير : Shift=J(10)-E(5)=5

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

var
input: Ansistring;


function Caesar(const chaine:string;const decallage:integer ): string;
var i,L: integer;
const
UPPER='ABCDEFGHIJKLMNOPQRSTUVWXYZ';
LOWER='abcdefghijklmnopqrstuvwxyz';
begin
  L := Length(chaine);
  result:=chaine;
  for i := 1 to L do
  begin
  if chaine[i] in ['A'..'Z'] then
  begin
  if (Pos(chaine[i],UPPER) + decallage) mod 26 =0 then Result[i] := UPPER[26]
  else
  Result[i] := UPPER[(Pos(chaine[i],UPPER) + decallage) mod 26];
  end;
  if chaine[i] in ['a'..'z'] then
  begin
  if (Pos(chaine[i],LOWER) + decallage) mod 26 =0 then Result[i] := LOWER[26]
  else
  Result[i] := LOWER[(Pos(chaine[i],LOWER) + decallage) mod 26];
  end;
  end;
end;


function IndexOfArray(const Value: integer; Items: array of integer): Integer;
var
  i: Integer;
begin
  Result := -1;
  for i := Low(Items) to High(Items) do
  begin
    if Value=Items[i] then
    begin
      Result := i;
      Break;
    end;
  end;
end;


function OccurrencesOfChar(const S: Ansistring; const C: char): integer;
var
  i: Integer;
begin
  result := 0;
  for i := 1 to Length(S) do
    if S[i] = C then
      inc(result);
end;


function GetMaxValue(MyArray : array of integer): integer;
var
  Idx: Integer;
begin
  Result := MyArray[Low(MyArray)];
  for Idx := Low(MyArray)+1 to High(MyArray) do
  begin
    if MyArray[Idx] > Result then
      Result := MyArray[Idx];
end;
end;


procedure TForm1.Memo1Change(Sender: TObject);
var
i : cardinal;
begin
Button1.Enabled:=false;


input:=Uppercase(memo1.Text);
 For i := 1 to length(input) do
 If (ord(input[i])<65) or (ord(input[i]) > 90) then
 Delete(input,i,1);


if length(input)=0 then exit;


Button1.Enabled:=true;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
IC: array [1..26] of integer;
i, Shift : integer;
const
C='ABCDEFGHIJKLMNOPQRSTUVWXYZ';
begin

for i:=1 to 26 do
IC[i]:=OccurrencesOfChar(input,C[i]) ;


if IndexOfArray(GetMaxValue(IC),IC) > 5 then Shift:=IndexOfArray(GetMaxValue(IC),IC)-4
                                        else Shift:=4-IndexOfArray(GetMaxValue(IC),IC);

Edit1.text:=Inttostr(Shift);
Memo2.text:=Caesar(Memo1.text,26-Shift); // to encrypt use Caesar(Memo1.text,Shift);
end;

4-خاتمة:
هنا نكون قد وصلنا إلى نهاية هذه المقالة البسيطة، أتمنى أن أكون قد وفقت في إيصال بعض المفاهيم وأن تعينه على التمرين القادم الذي سأطرحه وسيكون مختلفا قليلا المرجو المشاركة مقبولة كي تستفيد من الشرح، التمرين القادم يخص Affine Cipher وبه عدة أسئلة ويتم التنقيط حسب درجة صعوبة السؤال.