Bài giảng Bảo mật thông tin - Bài 4: Mã hóa công khai RSA

Trình bày: Ths. Lương Trần Hy Hiến http://hienlth.info/hutech/baomatthongtin

1. Lý thuyết số

2. Mã hóa công khai

3. RSA

2

 Phép chia modulo: phép chia lấy dư

a mod n = r với a ≥ 0; n > 0; 0 ≤ r ≤ n-1

 Đồng dư trong phép chia modulo cho n: a ≡ b (mod n) hay a ≡ b mod n  Phép toán modulo phân hoạch tập số tự nhiên N thành n lớp tương đương đồng dư - ứng với các giá trị của r trong tập {0, 1, 2, 3, …, N-1}. VD: N = 4 có 4 lớp tương đương: {0, 4, 8, 12, 16 …}, {1, 5, 9, 13, 17 …}, {2, 6, 1, 14, 18 …}, {3, 7, 11, 15, 19 …}

3

Một số tính chất của modulo:

 (a + b) mod n = [(a mod n) + (b mod n)] mod n

 (a - b) mod n = [(a mod n) - (b mod n)] mod n

 (a x b) mod n = [(a mod n) x (b mod n)] mod n

4

 Ước số:

 gcd(a, b) : ước chung lớn nhất của 2 số, tìm

Nếu a mod n = 0 nghĩa là a chia hết cho n (𝒂 ⋮ 𝒏), hay n là ước số của a (n | a).

theo thuật toán Euclid.

 Số nguyên tố:

 Số nguyên tố cùng nhau:

p được gọi là số nguyên tố nếu p chỉ chia hết cho 1 và chính nó.

gcd(a,b) = 1 thì a, b nguyên tố cùng nhau, kí hiệu: a  b

5

 Phần tử nghịch đảo của phép nhân modulo:  Nếu a n thì:  w sao cho a.w  1 (mod n).  w dgl phần tử nghịch đảo trong phép chia mod

 Ví dụ: n = 10, a = 7 là hai số nguyên tố cùng nhau, do đó tìm được a-1 = 3 (21 ≡ 1 mod 10)

n, kí hiệu a-1.

6

 Nếu p là số nguyên tố và a là số nguyên không

 Ví dụ:

 p = 5, a = 7  74= 49.49 = 2401, 2401 ≡ 1 mod 5  p = 7, a = 4  46= 64.64 = 4096, 4096 ≡ 1 mod 7

chia hết cho p thì ap-1 ≡ 1 mod p

7

 Tính y từ a, x và n là các số nguyên:

 VD: n = 19, a và x = 1..18

y = ax mod n = (a.a … a) mod n (chỉ xét n nguyên tố).

8

 n = 19, a, x = 1..18  Nhận xét:

 hàng a = 11 lặp lại theo chu kỳ 3 giá trị 11, 7, 1.  Cần quan tâm hàng nào đủ giá trị (không tạo

 Như vậy chỉ có a = 2, 3, 10, 13, 14, 15 thì phép

chu kỳ)  hàng a = 2, 3, 10, 13, 14, 15.

 Tổng quát với mỗi n chỉ có một số trường hợp

lũy thừa modulo trên mới khả nghịch.

của a thì phép lũy thừa là khả nghịch  a được gọi là primitive root của n

9

10

 Còn gọi là mật mã hai khóa hay bất đối xứng  Các giải thuật khóa công khai sử dụng 2 khóa

 Một khóa công khai ▪ Ai cũng có thể biết ▪ Dùng để mã hóa thông báo và thẩm tra chữ ký

 Một khóa riêng

▪ Chỉ nơi giữ được biết ▪ Dùng để giải mã thông báo và ký (tạo ra) chữ ký

 Có tính bất đối xứng

 Bên mã hóa không thể giải mã thông báo  Bên thẩm tra không thể tạo chữ ký

 Có thể phân ra 3 loại ứng dụng

 Mã hóa/giải mã

▪ Đảm bảo sự bí mật của thông tin

 Chữ ký số

▪ Hỗ trợ xác thực văn bản

 Trao đổi khóa

▪ Cho phép chia sẻ khóa phiên trong mã hóa đối xứng

 Một số giải thuật khóa công khai thích hợp cho

cả 3 loại ứng dụng; một số khác chỉ có thể dùng cho 1 hay 2 loại.

Kẻ phá mã

Đích B

Nguồn A

Giải thuật giải mã

Nguồn th. báo

Giải thuật mã hóa

Đích th. báo

Nguồn cặp khóa

14

15 Khóa ngẫu nhiên

Alice

Bob

Mã hóa

Giải mã

Khóa công khai của Bob

Khóa riêng của Bob

 Bên B dễ dàng tạo ra được cặp (KUb, KRb)  Bên A dễ dàng tạo ra được C = EKUb  Bên B dễ dàng giải mã M = DKRb (C)  Đối thủ không thể xác định được KRb khi biết

(M)

KUb

 Đối thủ không thể xác định được M khi biết KUb

 Một trong hai khóa có thể dùng mã hóa trong

(EKRb

và C

khi khóa kia có thể dùng giải mã  M = DKRb (M)) (M)) = DKUb (EKUb  Không thực sự cần thiết

 Không thể tìm kiếm vét cạn  Khối lượng cần tính toán là rất lớn  không thể

tìm khóa thứ 2.

 Mã công khai thường chậm hơn khá nhiều so với mã đối xứng, nên nó thường được dùng mã những thông tin nhỏ quan trọng

18

 Đề xuất bởi Ron Rivest, Adi Shamir và Len

 Hệ mã hóa khóa công khai phổ dụng nhất  Mã hóa khối với mỗi khối là một số nguyên < n  Thường kích cỡ n là 1024 bit ≈ 309 chữ số thập phân

 Đăng ký bản quyền năm 1983, hết hạn năm

Adleman (MIT) vào năm 1977

 An ninh vì chi phí phân tích thừa số của một số

2000

nguyên lớn là rất lớn

19

 Mỗi bên tự tạo ra một cặp khóa công khai -

khóa riêng theo các bước sau: 1. Chọn ngẫu nhiên 2 số nguyên tố đủ lớn p  q 2. Tính n = pq và (n) = (p-1)(q-1) – dùng ĐL

Trung Hoa để giảm bớt tính toán.

3. Chọn ngẫu nhiên khóa mã hóa e sao cho 1 < e < (n) và gcd(e, (n)) = 1 (nguyên tố cùng nhau)

4. Tìm khóa giải mã d ≤ n thỏa mãn e.d ≡ 1 mod

(n) (ed – 1 chia hết cho (n)) 5. Công bố khóa công khai KU = {e, n}

Giữ bí mật khóa giải mã riêng KR = {d, n} ▪ Các giá trị bí mật p và q bị hủy bỏ

Cho biết (e,n) và (d,n) 1. Để mã hóa 1 thông báo nguyên bản M, bên gửi

2. Để giải mã bản mã C nhận được, bên nhận

thực hiện:  Lấy khóa công khai của bên nhận KU = {e, n}  Tính C = Me mod n

 Lưu ý là thông báo M phải nhỏ hơn n

 Phân thành nhiều khối nếu cần

thực hiện:  Sử dụng khóa riêng KR = {d, n}  Tính M = Cd mod n

 Theo ĐL Ole: aФ(n)mod N = 1 trong đó gcd(a, N)=1.

 Ta có N=p.q, với Ф(N)=(p-1)(q-1), e.d=1 mod Ф(N).

e.d=1+k.Ф(N) đối với một giá trị k nào đó.

 Suy ra: Cd = (Me)d = M1+k.Ф(N) = M1.(MФ(N))k

 Nên Cd mod N = M1.(1)k modN

= M1 mod N = M mod N

22

 Theo định lý Euler

  a, n: gcd(a, n) = 1  a(n) mod n = 1  (n) là số các số nguyên dương nhỏ hơn n và nguyên

tố cùng nhau với n

 Đối với RSA có

 n = pq với p và q là các số nguyên tố  (n) = (p - 1)(q - 1)  ed ≡ 1 mod (n)   số nguyên k: ed = k(n) + 1  M < n

 Có thể suy ra

 Cd mod n = Med mod n = Mk(n) + 1 mod n = M mod n =

 Chọn 2 số nguyên tố p = 17 và q = 11  Tính n = pq = 17  11 = 187  Tính (n) = (p - 1)(q - 1) = 16  10 = 160  Chọn e: gcd(e, 160) = 1 và 1 < e < 160; lấy e =

 Xác định d: de ≡ 1 mod 160 và d ≤ 187

 Công bố khóa công khai KU = {7, 187}  Giữ bí mật khóa riêng KR = {23, 187}  Hủy bỏ các giá trị bí mật p = 17 và q = 11

Giá trị d = 23 vì 23  7 = 161 = 1  160 + 1

Mã hóa

Giải mã