دستورالعملها
یک پیادهسازی از رمز آفین بسازید؛ یک سیستم رمزنگاری باستانی که در خاورمیانه پدید آمد.
رمز آفین نوعی رمز جایگزینی تکالفبایی است.
هر نویسه به معادل عددی خودش نگاشت میشود، با یک تابع ریاضی رمزگذاری میشود و سپس به حرفی تبدیل میشود که با مقدار عددی جدیدش متناظر است.
هرچند همهی رمزهای تکالفبایی ضعیف هستند، رمز آفین بسیار قویتر از رمز اتبش است، چون کلیدهای بسیار بیشتری دارد.
رمزگذاری
تابع رمزگذاری چنین است:
E(x) = (ai + b) mod m
که در آن:
-
i اندیس حرف است، از 0 تا طول الفبا منهای ۱.
-
m طول الفبا است.
برای الفبای لاتین، m برابر 26 است.
-
a و b اعداد صحیحی هستند که کلید رمزگذاری را تشکیل میدهند.
مقادیر a و m برای موفقیت رمزگشایی خودکار باید متقابلاً اول (یا نسبت به هم اول) باشند؛ یعنی تنها عامل مشترکشان عدد 1 باشد (اطلاعات بیشتر را میتوانید در مقالهی ویکیپدیا دربارهی اعداد صحیح متقابلاً اول پیدا کنید).
اگر a نسبت به m متقابلاً اول نباشد، برنامهی شما باید نشان دهد که این یک خطاست.
در غیر این صورت باید با کلید دادهشده رمزگذاری یا رمزگشایی کند.
در این تمرین، رقمها ورودی معتبری هستند، اما رمزگذاری نمیشوند.
فاصلهها و نویسههای نشانهگذاری نادیده گرفته میشوند.
متن رمزشده در گروههایی با طول ثابت نوشته میشود که با فاصله از هم جدا شدهاند؛ اندازهی سنتی هر گروه 5 حرف است.
این کار حدسزدن متن رمزشده را بر پایهی مرزهای واژهها دشوارتر میکند.
رمزگشایی
تابع رمزگشایی چنین است:
D(y) = (a^-1)(y - b) mod m
که در آن:
-
y مقدار عددی یک حرف رمزشده است؛ یعنی y = E(x)
- توجه به این نکته مهم است که
a^-1 وارون ضربی پیمانهای (MMI) برای a mod m است
- وارون ضربی پیمانهای تنها زمانی وجود دارد که
a و m متقابلاً اول باشند.
وارون ضربی پیمانهای a عددی مانند x است که باقیماندهی تقسیم ax بر m برابر 1 باشد:
ax mod m = 1
اطلاعات بیشتر دربارهی این که چطور وارون ضربی پیمانهای را پیدا کنیم و معنای آن چیست، در مقالهی مرتبط ویکیپدیا آمده است.
مثالهای کلی
- رمزگذاری
"test" با کلید a = 5 و b = 7 خروجی "ybty" را میدهد
- رمزگشایی
"ybty" با کلید a = 5 و b = 7 خروجی "test" را میدهد
- رمزگشایی
"ybty" با کلید اشتباه a = 11 و b = 7 خروجی "lqul" را میدهد
- رمزگشایی
"kqlfd jzvgy tpaet icdhm rtwly kqlon ubstx" با کلید a = 19 و b = 13 خروجی "thequickbrownfoxjumpsoverthelazydog" را میدهد
- رمزگذاری
"test" با کلید a = 18 و b = 13 یک خطاست، چون 18 و 26 متقابلاً اول نیستند
مثالی از یافتن وارون ضربی پیمانهای (MMI)
یافتن وارون ضربی پیمانهای برای a = 15:
(15 * x) mod 26 = 1-
(15 * 7) mod 26 = 1، یعنی 105 mod 26 = 1
-
7 وارون ضربی پیمانهای 15 mod 26 است
