Rabin algoritmi

1979 yilda Maykl Rabin taklif qilgan tizim. RSA ga o'xshaydi, lekin shifrlashda e = 2 — ya'ni xabarni kvadratga ko'taradi. Uning xavfsizligi faktorlash muammosiga teng kuchli ekanligi matematik isbotlangan — RSA uchun bunday isbot yo'q.

Kalitlar

Ikkita katta tub son p va q tanlanadi, ularning har biri 4 ga bo'linganda 3 qoldiq berishi kerak: p mod 4 = 3, q mod 4 = 3 (bu kvadrat ildizni oson hisoblash uchun). Yopiq kalit — (p, q), ochiq kalit — n = p·q. Xabar M < n bo'lishi kerak, aks holda bo'laklarga ajratiladi.

Ochish

1. m₁ = C^(p+1)/4 mod p, m₂ = p − m₁
2. m₃ = C^(q+1)/4 mod q, m₄ = q − m₃
3. a = p·(p⁻¹ mod q), b = q·(q⁻¹ mod p)
4. M₁ = (a·m₃ + b·m₁) mod n, M₂ = (a·m₄ + b·m₁) mod n, M₃ = (a·m₃ + b·m₂) mod n, M₄ = (a·m₄ + b·m₂) mod n

Hosil bo'lgan to'rt sondan bittasi asl xabar, qolgan uchtasi — «yolg'on». Qaysi biri to'g'riligini aniqlash uchun xabarga ma'lum tuzilma (masalan, ASCII oralig'i yoki nazorat belgilari) kiritiladi.

Kitobdagi misol: p = 43, q = 19, M = «OLTI»

n = 817. «O» = 79 → C = 79² mod 817 = 522. Ochish: m₁ = 522¹¹ mod 43 = 36, m₂ = 7, m₃ = 522⁵ mod 19 = 16, m₄ = 3; a = 43·4 = 172, b = 19·34 = 646 → M = {681, 79, 738, 136}. 127 dan kichigi — 79 = «O».