RSA(rivest-shamir-adleman)
區段加密法,用指數運算
使用fractorization(因數分解)原理
publickey可以是任何長度,典型用法是512bit,最高支援4096bit
可自己決定加密訊息區塊長度,但最好不要超過key的長度
須先產生key pair,也就是publickey及privatekey
攻擊方法：暴力法,數學攻擊法,計時攻擊法
產生key步驟
1找2個大質數p及q
ps:小於100的質數有2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97
2計算N=p*q及M=euler(N)
3產生public key(e,N),e需滿足gcd(e,M)=1
4產生private key(d,N),d需滿足(e*d)mod M=1
ex:
1
設p=3,q=5 ,pq互為質數
2
N=pq=3*5=15
M=euler(15)=(p-1)(q-1)=(3-1)(5-1)=8
3
gcd(e,8)=1
e可以為1,3,5,7任一數,假設e=3
(3,15)為public key
4
(3*d)mod 8=1
d可以為3,11,…,但3和e相同,所以選11當d
(11,15)為private key
ex:
N=35=p*q=7*5
M=24=eular(35)=(7-1)(5-1)
gcd(e,24)=1,e=1,5,7,11,13,17,19,23,we select e=5 ,so public key=(5,35)
(5*d)%24=1,select d=29 ,so private key=(29,35)
加解密步驟
設public key=(e,N),private key=(d,N),明文為P,密文為C
加密方式:用公鑰加密
C=encrypt(P,(e,N))=(P^e)mod N
解密方式:用私鑰解密
P=decrypt(C,(d,N))=(C^d)mod N
ex:
設public key=(3,15),private key=(11,15),P=7
加密方式:(7^3)mod15=343mod15=13
產生”密文13″
解密方式:(13^11)mod15=(169*169*…*13)mod15=(4*4*4*4*4*13)mod15=(4*13)mod15=7
產生”明文7″
ex:
設public key=(5,35),private key=(29,35),P=10
encryption
C=(10,(5,35))=(10^5)mod35=5
decryption
P=(5,(29,35))=(5^29)mod35=(125*125*..5*5)mod35=(20*20*…5*5)mod35=(20*5*5)mod35=10
數位簽章步驟
設public key=(e,N),private key=(d,N),設息為M,簽章為S
簽章產生方式:用私鑰產生簽章
1 S=signature(M,(d,N))=(M^d)mod N
2 將S和M放在一起
簽章驗證方式:用公鑰驗證簽章
1 M=verify(S,(e,N))=(S^e)mod N
2 若原來的M和驗證出來的M相同,表示確定訊息M為私鑰擁有者所簽署
ps:
尤拉函數
euler(n)
小於n的整數中與n互質的整數個數
ex:
1
euler(15)=(3-1)(5-1)=8
證明:計算小於15的整數與15互質的整數,算法如下
gcd(15,1)=1
gcd(15,2)=1
gcd(15,4)=1
gcd(15,7)=1
gcd(15,8)=1
gcd(15,11)=1
gcd(15,13)=1
gcd(15,14)=1
因此小於15的整數中與15互質的整數為1,2,4,7,8,11,13,14,共8個
2
euler(6)=(3-1)(2-1)=2
小於6的整數中與6互質的整數為1,5
ps:
建議RSA的金鑰長度至少要1024bit以上
A. Lenstra(1994)可成功地解出RSA 129bit
ps:
常見RSA攻擊:
chosen-ciphertext
common modulus attack