بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 29: کلید عمومی با عدد Public Key with Numbers

تا حالا رمزها یک کلید مشترک داشتند. حالا دو کلید می‌سازیم: یکی عمومی برای قفل کردن، یکی خصوصی برای باز کردن. با یک RSA اسباب‌بازی و اعداد کوچک، رمز می‌کنیم، باز می‌کنیم و یک امضای دیجیتال می‌سازیم.

در این جلسه یاد می‌گیری

درس

⚠️ RSA این جلسه با اعداد اسباب‌بازی است و فقط برای فهمیدن ایده؛ در دنیای واقعی هیچ‌وقت رمز خودت را نساز، از کتابخانه‌های آزمایش‌شده استفاده کن. کلید خصوصی دیگران مال آن‌هاست: تلاش برای حدس زدن یا شکستن کلید دیگران، حتی اگر «کوچک» باشد، بدون اجازه مجاز نیست. اگر جایی کلید خصوصی کسی را به اشتباه دیدی، به او خبر بده.

مشکل رمزهای قبلی: فرستنده و گیرنده باید یک کلید مشترک داشته باشند. ولی کلید را چطور به کسی برسانیم که هیچ‌وقت ندیده‌ایمش؟ راه حل: دو کلید. کلید عمومی مثل یک قفل باز است که به همه می‌دهی؛ هرکس می‌تواند با آن پیام را قفل کند. کلید خصوصی تنها کلیدی است که آن قفل را باز می‌کند و فقط پیش توست.

RSA این کار را با عدد انجام می‌دهد. دو عدد اول کوچک انتخاب می‌کنیم: p = 61 و q = 53. ضربشان n = 3233 است. عدد e = 17 را به عنوان کلید عمومی و d = 2753 را به عنوان کلید خصوصی داریم (ریاضیِ پیدا کردن d را فعلاً قبول می‌کنیم؛ نکته این است که از n و e به تنهایی، پیدا کردن d برای عددهای بزرگ تقریباً غیرممکن است).

p, q = 61, 53
n = p * q          # 3233  (public)
e = 17             # public exponent
d = 2753           # PRIVATE exponent - keep it secret
print(n)

رمز کردن یک عدد m (کوچک‌تر از n): c = pow(m, e, n) یعنی m به توان e، باقی‌مانده بر n. باز کردن: pow(c, d, n) که دوباره m را می‌دهد. pow با سه ورودی خیلی سریع است، حتی برای توان‌های بزرگ.

m = 65
c = pow(m, e, n)
print(c)                 # 2790
print(pow(c, d, n))      # 65

پیام متنی را حرف به حرف رمز می‌کنیم: ord("H") عدد ۷۲ است؛ آن را رمز می‌کنیم و لیستی از عددها می‌گیریم. گیرنده هر عدد را با کلید خصوصی باز و با chr دوباره حرف می‌کند. (RSA واقعی هرگز حرف‌به‌حرف کار نمی‌کند، چون همان حرف همیشه همان عدد می‌شود؛ این فقط برای یادگیری است.)

def encrypt(text):
    return [pow(ord(ch), e, n) for ch in text]

def decrypt(numbers):
    return "".join(chr(pow(c, d, n)) for c in numbers)

secret = encrypt("HI")
print(secret)            # [3000, 1486]
print(decrypt(secret))   # HI

و حالا یک جادوی دوم: اگر جای کلیدها را عوض کنیم، امضا می‌سازیم. من با کلید خصوصی‌ام چیزی را «قفل» می‌کنم؛ هر کسی با کلید عمومی من می‌تواند بازش کند و مطمئن شود که فقط من می‌توانستم آن را بسازم. برای پیام طولانی، اول هش پیام را می‌گیریم (int(hexdigest, 16) % n) و روی همان عدد امضا می‌زنیم.

import hashlib

def digest(text):
    return int(hashlib.sha256(text.encode()).hexdigest(), 16) % n

def sign(text):
    return pow(digest(text), d, n)          # private key

def verify(text, signature):
    return pow(signature, e, n) == digest(text)   # public key

s = sign("pay 10")
print(s)                              # 1270
print(verify("pay 10", s))            # True
print(verify("pay 1000", s))          # False  <- changed message

خلاصه به زبان ساده: رمز کردن = قفل با کلید عمومیِ گیرنده، باز با کلید خصوصیِ گیرنده (محرمانگی). امضا = قفل با کلید خصوصیِ فرستنده، باز با کلید عمومیِ فرستنده (اصالت و درستی). HTTPS، به‌روزرسانی‌های نرم‌افزار و پیام‌رسان‌های امن همه روی همین دو ایده ساخته شده‌اند، فقط با عددهای چندصد رقمی.

اشتباه‌های رایج: ۱) جابه‌جا کردن e و d: رمز با e، باز با d؛ امضا برعکس. ۲) فراموش کردن ورودی سوم pow (بدون n عددها غول‌پیکر می‌شوند). ۳) رمز کردن عددی بزرگ‌تر از n که دیگر درست برنمی‌گردد. ۴) فکر کردن که این RSA اسباب‌بازی امن است؛ n = 3233 را هر کسی در یک ثانیه به 61 × 53 می‌شکند.

مثال‌های این جلسه

چالش‌ها

  1. Lock a Number (آسان)
  2. Unlock It (آسان)
  3. Letter by Letter (متوسط)
  4. Round Trip (متوسط)
  5. Sign It (سخت)
  6. Who Sent It? (سخت)
  7. Lock a List (متوسط)
  8. Unlock the Message (متوسط)
  9. Check the Signature (سخت)

بیشتر بخوان

← جلسه‌ی 28: پروژه: دفترچه‌ی یادداشت ضدخراب جلسه‌ی 30: کد یک‌بارمصرف واقعی →