An toàn và An ninh thông tin
Nguyn Linh Giang.
B môn Truyn thông
và Mng máy tính.
Phng pháp RSA
Thut toán mã hoá công khai RSA
 C s lý thuyt
 Sđmã hóa và gii mã
 To khóa
 Vn đ tính toán trong RSA
 Thám mã RSA
Lý thuyt s
 S hc modun
 nh lý Euler và đnh lý Fermat
 Kim tra s nguyên t
 Thut toán Euclid
 nh lý s d Trung Hoa
 Sinh gi ngu nhiên các s nguyên ln
S hc modun
 nh lý v s d. Cho mt s nguyên dngnvà mt s nguyêna.Khi
đó tn ti duy nht các s qvà rvi,sao choa =qn+ r.
rgi là s d ca phép chia a cho n.
 nh ngha s d. Cho mt s nguyên dng n và s nguyêna.Ký hiu
a mod n là s d khi chia a cho n.
a = x n + (a mod n)
 nh ngha2.Hai s avà b đc gi là đng d theo mođunnnua
mod n = b mod n. Và vit là a b (mod n)
 Ví d: 11 = 1 x 7 + 4 => 11 mod 7 = 4
-11= (-2) x 7+ 3=> -11mod 7= 3
73 4 (mod 23)
≡

 nh lý Fermat
 Hàm Euler
 nh lý Euler
nh lý Fermat
 Phát biu
Nuplà s nguyên t và alà s nguyên dng không chia ht chopthì
 Chng minh
 Ví d
a = 7, p = 19
 nh lý trên có th phát biu di dng tng đng nh sau:
Nuplà s nguyên t và alà mt s nguyên dng bt k,thì
p1
a 1(mod p)
−
≡
p
aa (mod p)≡
Hàm Euler
 Hàm Euler đc ký hiu là là s các s nguyên dng nh hnnvà
nguyên t cùng nhau vin.
 Ví d
= 12 (12 s nguyên đó là [1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20])
(n)
φ
(21)φ
nh lý Euler
 Phát biu
 Ví d
a = 3; n = 10;
 Chng minh

Thut toán Euclid (tip)
 Tìm phn tđi xng
Thut toán Euclid m rng s tr v phn tđi xng cadnu gcd(d, f)
= 1.
nh lý s d Trung Hoa
 nh lý
̇ Hai kt qu ca đnh lý s d Trung Hoa
̇ ng dng ca đnh lý s d Trung Hoa
̇ Ví d
Sinh gi ngu nhiên các s nguyên ln
 B sinh s gi ngu nhiên
K thut đc s dng rng rãi trong vic sinh gi ngu nhiên là phng
pháp đng d tuyn tính ln đu tiên đc đ xut bi Lehmer.
 Sinh s gi ngu nhiên da trên k thut mt mã
 B sinh s gi ngu nhiên Blum Blum Shub
Sđmã hóa và gii mã RSA
 Xut x
– RSA do Ron Rivest, Adi Shamir và Len Adlenman
phát minh nm 1977;
– H thng mã khoá công khai ph bin và đa nng:
 c s dng trong các ng dng mã hóa/gii mã;
 Chng thc;
 Phân phi và trao đi khoá.
 Thut toánRSA:
– Phng pháp mã hóa khi;
 Vn bn rõ và vn bn mt là các s nguyên có
giá tr t 0 đnn-1, n – s nguyên ln;
 Mi khi có giá tr nh hnn.Nh vy, kích
thc ca khi(s bít) nh hn hoc bng
log

Thc hin gii thut
 Mã hoá và gii mã
– Vn đ trong thut toán mã hoá và gii mã RSA là vic thc hin phép toán lu
tha và phép toán đng d vi s nguyên ln.
– Gii quyt da trên tính cht ca phép toán mođun:
[(a mod n) x (b mod n)] mod n = (a x b) mod n
Thc hin gii thut(tip)
 Sinh khoá
-Xác đnh s nguyên t p, q (s dng thut toán Miller – Rabin)
1. Chn mt s nguyên l nngu nhiên(s dng b sinh s gi ngu nhiên).
2. Chn mt s nguyêna < nngu nhiên.
3. Thc hin thut toán xác sut đ kim tra s nguyên t.Nu n test thành
công thì loi b giá tr nvà quay li bc1.
4. Nu n test thành công vi s lng test đ,chp nhnn;mt khác, quay li
bc2.
-Chnd
-Tính e t dvà (n) (s dng thut toánEuclid)
φ
Tính bo mt ca gii thutRSA
 Tn công vét cn
 Tn công toán hc
 Tn công da vào thi gian