RSA.md

MODULO

a | b
  |----
r | t

19 | 7
   |----
 5 | 2

• 19≡5[7] (19 đồng dư vs 5 mod 7 - 5 là phần dư của 19 cho 7)

Tổng quát: a≡b[m] => a=km+b
Đặc biệt: b=0 => a=km => a≡0[m]

• Phép tính đồng dư modulo m được gọi là phép tính trong Z/mZ

Greatest Common Divisor

Ví dụ: 19 và 7

a	b	r
19	7	5
7	5	2
5	2	1
2	1	0
(19, 7) = 1

Ví dụ: 19 và

a	b	r
62	8	6
8	6	2
6	2	0
(19, 7) = 2

Phần thử nghịch đảo

• Trong R, a đảo là số nghịch đảo của a nếu a đảo x a = 1
• Trong Z/mZ, a đảo là số nghịch đảo của a nếu a đảo x a = 1[m]

1=3*19-8*7 => 3x19≡1[7] (phép tính (mod 7 nên -8*7) =0)
3 là phần tử nghịch đảo của 19 trong Z/7Z

1=3*19-8*7 => -8x7≡1[19] (phép tính (mod 19 nên 3*19) =0)
-8 là phần tử nghịch đảo của 7 trong Z/19Z

• Chỉ những số nguyên tố cùng nhau mới có phần tử nghịch đảo (ví dụ 19 và )

RSA

• Cho 2 số nguyên tố p,q
• Tính n=pq, m=(p-1)(q-1)
• Cho e∈N, (m, e)=1 (nguyên tố cùng nhau)
• Tính d với e*d=1[m] (d=e^-1)

Sử dụng: Giá sử mã hóa số x sang số y

• Mã hóa: x^e[n]=y
• Giải mã: y^d[n]=x n,e: public key, d: private key.

Vận hành của mã RSA

Alice:

p=7, q=11
=> n=77, m=60
=> Tìm được e=7 (nguyên tố cùng nhau với 60)
=> Tìm được d=43[60] (43 là phần tử nghịch đảo của 7 trong Z/60Z)

public key: (77, 7)
private key: (43)

Bob:

p=5, q=11
=> n=55, m=40
=> Tìm được e=3 (nguyên tố cùng nhau với 40)
=> Tìm được d=27[40] (27 là phần tử nghịch đảo của 3 trong Z/40Z)

public key: (55, 3)
private key: (27)

• Alice và Bob trao đổi public key cho nhau.
• Alice muốn gửi số 13 cho Bob: 13^3 mod 55 = 52
• Bob nhận được số 52: 52^27 mod 55 = 13
• Bob muốn gửi số 13 cho Alice: 28^7 mod 55 = 52
• Alice nhận được số 52 và muốn giải mã: 52^27 mod 55 = 13