TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 1
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
TS. Phạm Việt Hà
MẬT MÃ HÓA HIỆN ĐẠI
Chương 4: Hệmật khóa công khai
MẬT MÃ HÓA HIỆN ĐẠI
Chương 4: Hệmật khóa công khai
Trang 2© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4. Hệmật khoá công khai4. Hệmật khoá công khai
4.1 HệmậtRSA
4.2 Hạtầng khóa công khai PKI
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 2
Trang 3© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
RSA là mã công khai đượcsángtạobởi Rivest, Shamir & Adleman ở
MIT (Trường Đạihọc Công nghệMassachusetts) vào năm 1977.
RSA là mã công khai đượcbiếtđến nhiềunhấtvàsửdụng rộng rãi
nhấthiệnnay.
RSA dựa trên các phép toán lũythừa trong trường hữuhạn các số
nguyên theo modulo nguyên tố. Cụthể, mã hoá hay giải mã là các
phép toán luỹthừa theo modulo sốrấtlớn.
Việcthámmã, tức là tìm khoá riêng khi biết khoá công khai, dựatrên
bài toán khó là phân tích mộtsốrấtlớnđórathừasốnguyên tố. Nếu
không có thông tin gì, thì ta phảilầnlượtkiểm tra tính chia hếtcủasố
đóchotấtcảcác sốnguyên tốnhỏhơncăncủa nó. Đây là việclàm
không khảthi!
Trang 4© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Người ta chứng minh đượcrằng, phép lũythừacần O((log n)3) phép toán,
nên có thểcoi lũythừa là bài toán dễ.
Cần chú ý rằng ở đây ta sửdụng các sốrấtlớn khoảng 1024 bit, tứclàcỡ
10350.
Tính an toàn dựavàođộ khó của bài toán phân tích ra thừasốcác sốlớn. Bài
toán phân tích ra thừasốyêu cầuO(e
logn log logn) phép toán, đây là bài toán
khó.
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 3
Trang 5© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Khởitạo khoá RSA
•Mỗingườisửdụng tạomộtcặp khoá công khai – riêng nhưsau:
–Chọnngẫu nhiên 2 sốnguyên tốlớnp vàq
–Tính sốlàm modulo củahệthống: N = p.q
•Ta đãbiếtФ(N)=(p-1)(q-1)
•Và có thểdùng Định lý Trung Hoa để giảmbớt tính toán
•Chọn ngẫu nhiên khoá mã e
•Trong đó 1<e< Ф(N), gcd(e,Ф(N))=1
•Giải phương trình sau để tìm khoá giải mã d sao cho
•e.d=1 mod Ф(N) với 0≤d≤ Ф(N)
•In khoá mã công khai KU={e,N}
•Giữ khoá riêng bí mật KR={d,p,q}
Trang 6© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Sử dụng RSA
•Để mã hoá mẩu tin, người gủi:
–Lấy khoá công khai của người nhận KU={e,N}
–Tính C=Memod N, trong đó 0≤M<N
•Để giải mã hoá bản mã, người sở hữu nhận:
–Sử dụng khóa riêng KR={d,p,q}
–Tính M=Cdmod N
•Lưu ý rằng bản tin M < N, do đó khi cần chia khối bản rõ.
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 4
Trang 7© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
CơsởcủaRSA
•Theo Định lý Ole
–a(n) mod N = 1 trong đó gcd(a,N)=1
–Ta có N=p.q
–Ф(N)=(p-1)(q-1)
–e.d=1 mod Ф(N)
–e.d=1+k.Ф(N) đốivớimột giá trịk nào đó.
•Suy ra
–Cd= (Me)d= M1+k.(N) = M1.(M(n))ksuy ra
–CdmodN = M1.(1)kmodN = M1modN = M modN
Trang 8© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Ví dụ
•Chọn các số nguyên tố: p=17 & q=11.
•Tính n = pq, n = 17×11=187
•Tính Ф(n)=(p–1)(q-1)=16×10=160
•Chọn e : gcd(e,160)=1; Lấy e=7
•Xác định d: de=1 mod 160 và d < 160
•Giá trịcần tìm là d=23, vì 23×7=161= 10×160+1
•In khoá công khai KU={7,187}
•Giữkhoá riêng bí mật KR={23,17,11}
TT CNTT HN Wednesday, April 25, 2012
CCIT/RIPT 5
Trang 9© 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Ví dụáp dụng mã RSA trên nhưsau:
•Cho mẩu tin M = 88 (vậy 88<187)
•Mã C = 887mod 187 = 11
•GiảimãM = 11
23 mod 187 = 88
•Có thể dùng định lý phầndưTrung Hoa để giải mã cho nhanh nhưsau:
–Tính 1123 mod 11 = 0
–Tính 1123mod 17 = (-6)23 mod 17 = (-6)16(-6)4(-6)2(-6) mod 17 =
c1= 3
Vì (-6)2mod 17 = 2, nên (-6)4mod 17 = 4, (-6)8mod 17 = -1,
(-6)16 mod 17 = 1
–11-1 mod 17 = (-6)-1 mod 17 = 14 nên 11(11-1 mod 17) = 11(14 mod
17) = c2= 154
–Vậy M = (3.154) mod 187 = 462 mod 187 = 88
Trang 10 © 2009 | CCIT/RIPT
VIỆN KHOA HỌC KỸ THUẬT BƯU ĐIỆN
TRUNG TÂM TƯ VẤN ĐẦU TƯ CHUYỂN GIAO CÔNG NGHỆ
4.1 HệmậtRSA4.1 HệmậtRSA
Mã hiệu quả:
•Mã sử dụng lũy thừa của khoá công khai e, nếu giá trị của e nhỏ thì
tính toán sẽ nhanh, nhưng dễ bị tấn công. Thường chọn e nhỏ hơn
hoặc bằng 65537 (216-1), tức là độ dài khoá công khai là 16 bit.
Chẳng hạn trong ví dụ trên ta có thể lựa chọn e = 23 hoặc e = 7.
•Ta có thể tính mã hoá nhanh, nếu biết n=pq và sử dụng Định lý phần
dư Trung Hoa với mẩu tin M theo các Modulo p và q khác nhau. Nếu
khoá công khai e cố định thì cần tin tưởng rằng khi chọn n ta luôn có
gcd(e,Ф(n)) = 1. Loại bỏ mọi p, q mà làm cho Ф(n) không nguyên tố
cùng nhau với e.