Mathematics of RSA

First posted on 17/10/2012

Berikut adalah contoh matematik ringkas tentang RSA encryption dan decryption.

  1. Alice pilih dua prime numbers yang besar, namanya p dan q. Nombor tu kena lah besar utk security yang mantap. Tapi untuk example ni guna yang kecik dulu, p = 17 dan q = 11. p dan q Alice pegang ni hendaklah di rahsia kan.
  2. Nombor p dan q tersebut haruslah di darabkan untuk hasilkan satu nombor yang baru, iaitu N. Dalam kes ni, N = 187. Sekarang Alice kena pilih satu lagi nombor namanya e. Katakan lah dia pilih e = 7.
  3. Sekarang Alice boleh kasi nombor N dan e dekat orang awam. Nombor nombor ini lah dinamakan Public-Key.
  4. Untuk proses encryption, message perlu di convert ke nombor, M. Nombor ini adalah dalam bentuk ASCII bits (1's and 0's). Bits ni pulak boleh diterjemahkan dalam bentuk decimal nombor.
  5. Equation untuk encryption: tex1
  6. So, Bob nak hantar Alice satu message, contoh nya satu huruf 'X'. Dalam bits, X = 1011000, bersamaan dengan 88 dalam decimal. Jadi, M = 88.
  7. Untuk encrypt X, Bob kena cari public-key Alice iaitu N = 187 dan e = 7.
    Dengan M = 88, formulanya tex2
  8. Here's how to solve this. Boleh jugak guna calculator and stuff tapi ada jalan alternatif. Kita tahu yang 7 = 4 + 2 + 1.
    tex3
    tex4
    tex5
    tex6
    tex7
    Bob boleh hantar encrypted message, C = 11 kepada Alice.
  9. Katakanlah ada seorang penjenayah ni nak eavesdrop message Bob tadi. Nama dia Eve. Eve dapat tap data dan received message Bob. Tapi dia tak boleh nak decipher message tu sebab exponentials dalam modular aritmetics (mod) adalah one-way function. Jadi susah nak reverse engineer nombor tersebut utk dapat kan plain text. Hanya Alice saja yang boleh encipher kat sini since dia ada value p dan q tadi. Dia boleh encipher untuk dapatkan d, decryption key aka Private-Key.
    Formula untuk decryption ialah
    tex8
    tex9
    tex10
    tex11
    Ada satu teknik dipanggil Euclid's algorithm boleh selesaikan d dengan pantas.
  10. Untuk decrypt message, Alice guna formula ini:
    tex12
    tex13
    tex14
    tex15
    tex16

Benda benda ni semua dipanggil RSA encryption. Direkacipta oleh abang Rivest, Shamir dan Adleman. RSA ialah one-way function, which is orang yang ada information tertentu saja yang boleh decrypt. Information tu ialah p and q tadi lah.


Sauce: Appendix E of 'The Code Book by Simon Singh'

Show Comments

Get the latest posts delivered right to your inbox.