Mathematics of RSA
First posted on 17/10/2012
Berikut adalah contoh matematik ringkas tentang RSA encryption dan decryption.
- 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.
- 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.
- Sekarang Alice boleh kasi nombor N dan e dekat orang awam. Nombor nombor ini lah dinamakan Public-Key.
- 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.
- Equation untuk encryption:
- So, Bob nak hantar Alice satu message, contoh nya satu huruf ‘X’. Dalam bits, X = 1011000, bersamaan dengan 88 dalam decimal. Jadi, M = 88.
- Untuk encrypt X, Bob kena cari public-key Alice iaitu N = 187 dan e = 7.
Dengan M = 88, formulanya - Here’s how to solve this. Boleh jugak guna calculator and stuff tapi ada jalan alternatif. Kita tahu yang 7 = 4 + 2 + 1.
Bob boleh hantar encrypted message, C = 11 kepada Alice. - 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
Ada satu teknik dipanggil Euclid’s algorithm boleh selesaikan d dengan pantas. - Untuk decrypt message, Alice guna formula ini:
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’