AlgoVerse

رمزنگاری RSA

کلید عمومی (e, n) و خصوصی (d, n) را از دو عدد اول می‌سازد، پیام را با توان پیمانه‌ای رمز می‌کند و دوباره برمی‌گرداند.

RSA (ریوست، شمیر و ادلمن، ۱۹۷۷) رمزنگاری با کلید عمومی است: هر کسی می‌تواند با کلید عمومی رمز کند، ولی فقط صاحب کلید خصوصی می‌تواند رمز را باز کند.

ادامه‌ی توضیح ↓
ورودی:
p=61 · q=53 · e=17 · message=65خروجی PDF

p = ۶۱ و q = ۵۳؛ n = ۳۲۳۳، φ = ۳۱۲۰، e = ۱۷ و d = ۲۷۵۳. پیام ۶۵ به ۲۷۹۰ رمز می‌شود و دوباره ۶۵ برمی‌گردد.

  1. def rsa(p, q, e, message):
  2. if not is_prime(p) or not is_prime(q) or p == q:
  3. return None
  4. n = p * q
  5. phi = (p - 1) * (q - 1)
  6. g, d = inverse(e, phi)
  7. if g != 1:
  8. return None
  9. private = (d, n)
  10. if message >= n:
  11. return None
  12. # pow(x, k, n) is modular exponentiation by repeated squaring (it has its own page).
  13. cipher = pow(message, e, n)
  14. back = pow(cipher, d, n)
  15. return cipher, back
  18. def is_prime(n):
  19. if n < 2:
  20. return False
  21. d = 2
  22. while d * d <= n:
  23. if n % d == 0:
  24. return False
  25. d = d + 1
  26. return True
  29. def inverse(a, n):
  30. # gcd(a, n) and the inverse of a mod n, by the extended Euclidean algorithm.
  31. r0, r1 = a, n
  32. s0, s1 = 1, 0
  33. while r1 != 0:
  34. q = r0 // r1
  35. r0, r1 = r1, r0 - q * r1
  36. s0, s1 = s1, s0 - q * s1
  37. return r0, s0 % n

ناوردا: e·d ≡ 1 (mod φ(n))، پس طبق قضیه‌ی اویلر (M^e)^d ≡ M (mod n) برای هر M < n.

شروع اجرا

n—
phi—
private—
cipher—
back—

متغیرهای محلی

p61
q53
e17
message65

نارنجی = در همین گام عوض شد

Call stack

  1. rsa()خط 1
گام ۱ از ۸۲
خط سیاه = modulus · خط نارنجی = گام کلیدیmodulus: 0/1 · phi: 0/1 · private_key: 0/1 · encrypt: 0/1 · decrypt: 0/1
    توضیح

    ایده

    RSA (ریوست، شمیر و ادلمن، ۱۹۷۷) رمزنگاری با کلید عمومی است: هر کسی می‌تواند با کلید عمومی رمز کند، ولی فقط صاحب کلید خصوصی می‌تواند رمز را باز کند.

    ساختن کلیدها

    1. دو عدد اول p و q انتخاب کن و n = p·q.
    2. φ = (p − 1)(q − 1).
    3. e را طوری انتخاب کن که با φ نسبت به هم اول باشد؛ d وارون e به پیمانه‌ی φ است (با اقلیدس توسعه‌یافته).

    کلید عمومی (e, n) و کلید خصوصی (d, n) است.

    رمز و رمزگشایی

    C = Mᵉ mod n و M = Cᵈ mod n (با توان پیمانه‌ای). چون e·d ≡ 1 (mod φ)، طبق قضیه‌ی اویلر جواب دوباره M می‌شود.

    چرا امن است؟

    برای پیدا کردن d باید φ را دانست، یعنی n را به p و q تجزیه کرد. برای عددهای چندصدرقمی هیچ روش سریعی شناخته نشده. عددهای اینجا عمداً کوچک‌اند تا بشود دنبالشان کرد.