- n = pq, where p and q are distinct primes.
- phi, φ(n) = (p-1)(q-1)
- e < n such that gcd(e, phi)=1
- d = e-1 mod phi.
- c = me mod n
參考影片:https://www.youtube.com/watch?v=QSlWzKNbKrU
1. 取兩個質數p及q越大越好,假設(p,q)=(3,11)
2. 令 n = p *q = 3 * 11 = 33
3. 根據定理, 在 n 的整數空間中與n互質的個數等於(p-1)*(q-1),該值就是phi(n),等於就是刪掉3的倍數及11的倍數,因此 phi(n)=2*10=20個:
1 2 3
12345678901234567890123456789012
VV VV VV V VV VV VV V VV VV VV
如果質數大於1時,通用公式為:(pi^ei -pi^ei')*...的總乘積,i是質數的個數
phi(3*11)=(3^(1)-3^(0))*(11^(1)-11^(0))=(3-1)*(11-1)=20
4. 選擇e < 33,且gcd(e,20)=1,也就是說與phi(n)互質的整數,例如3為例:
因為 gcd(3,20) =1 故必定存在 d*3 = 1 mod 20
5. 求出 d = e^-1 mod phi(33)
因為 phi(33) = 20 , e=3
6. (33,3)就是公鑰,7就是私鑰,伺服器將(33,3)傳給使用者要求使用在指數空間編碼,例如將整數a用a^e mod n 來編碼,以a=4為例,公鑰e=4,n=33:
4^3 mod 33 = 64 mod 33 = 31
將4編碼成31,傳回伺服器
7.伺服器同樣使用指數解碼,但改用d來解碼,指數d=7,n=33
31^7 mod 33 = (-2)^7 mod 33 = -128 mod 33 = -4*33+4 mod 33
= 4 mod 33 --> 解碼等於 4,正好就是使用者傳的資料!
8.Euler's theorem:
其中 gcd(a,n)=1
如果p是質數,與p互質(coprime)的個數1..p-1全與p互質=phi(p)= p-1,
因此 a^(phi(p))=a^(p-1) = 1 mod p,兩邊同乘以 a
a^p = a mod p
上式就是Fermat's little theorem定理:當p是質數時對任何整數a而言
a^p=a mod p
9.來看編碼/解碼程序中 e,d,n,phi(n)關係:
指數e,d是由phi(n)整數空間推導出來,因為gcd(e,phi(n))=1,因此d必定存在,且互為倒數,換句話說:
e*d = 1 mod phi(n) => ed=1+phi(n)*k, k 是整數
而 a^(ed) = a^(1+phi(n)*k)= a * a^(phi(n)*k)
上述尤拉定理 a^phi(n) = 1 mod n,將上式映射到 mod n 空間就會得到:
a^ed mod n = a * a^(phi(n)*k) mod n = a *1^k mod n = a mod n
詳細參考:https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
Alice 選擇私鑰 a, 計算公鑰 Pa = r^a mod n, 並將 Pa 傳給 Bob
Bob 選擇私鑰 b, 計算公鑰 Pb = r^b mod n, 並將 Pb 傳給 Alice
兩人收到後再用私鑰用同樣函式計算出 key
Alice 收到 r^b mod n 計算出 (r^b)^a mod n = r^(ba) mod n
Bob 收到 r^a mod n 計算出 (r^a)^b mod n = r^(ab) mod n
之後使用 a*b 來當 key 加密之後要傳輸的資料
11 這樣資料密鑰交換有沒問題呢? 如果駭客監聽到 Pa 或 Pb,而且他也知道r及n,想要破解a或b
Pa = r^a mod n
Pb = r^b mod n
兩條方程式2個變數(a,b),因為對稱的關係,一條方程式各有一個變數,看似好像有解,但是很難解
單純看一個方程式就好,因為它是mod n的運算關係式,已知 p, r, n想要求出 a,也就是說:
p = r^a mod n --- (1)
因為 p 是餘數,且包含r,a,n等全都是整數,因此可以假設另一個整數k可以讓下列關係式成立:
r^a = p + k*n --- (2)
上式經 mod n 運算後, 最後一項(k*n)會被消去成0,就等同 r^a mod n = p,因為係數全都是整數的關係,如果想要解方程式可以利用嘗試錯誤法勉強可以將上式(1)湊出答案.也就是說讓a從 1, 2,3 ... 一直不停的帶進方程式裏面,再求出兩邊的答案,當兩邊等式成立時就找到答案了.但萬一a,p,n及r都是很大的一個整數的話,比如說 1024 位元組的一個數字,大約是2^1024 次方數量級的一個大整數的話,可是要花費很長一段時間的.
12 ElGamal 加解密演匴法:
1.Alice選一個質數=p及產生器=g,並挑選私鑰=a {2,3,...,p-2},用指數函數計算出h,公鑰就是(p,g,h)可以公開傳給Bob:
h = g^a mod p --- (1)
2.Bob利用Alice傳來的公鑰(p,g,h)將明文m加密,但他先隨機挑選一個亂數:
k 條件式: 滿足1 < k < p-1 且 gcd(k,p-1)=1
也就是說k與p-1必需互質無公因數.同樣使用指數函數計算,並將明文m編碼成(r,s)兩個數傳回給Alice:
r = g^k mod p --- (2)
s = m * h^k mod p --- (3)
3. Alice收到Bob所傳來的的(r,s)後,用私鑰a並用公式計算就可解碼:
m ≡ s * (r^−a) mod p --- (4)
(-a) = p - 1 - a (5)
4. 理由是將(2),(3)式將帶入(4)式就可一窺之迷:
(4) (2) (3)
s * r^-a mod p = m * h^k * (g^k)^-a mod p, 再把(1)式 h = g^a 帶入
= m * (g^a )^k * (g^k)^-a mod p 可以看到後面兩項互相消去了,得到明文 m
= m mod p
5. 在第4式中有一個難題是 r^-a mod p = (r^a)^-1 mod p 是什麼? 它就是指數r^a的模p倒數.當r,a,p已知,因為 p 是質數,要求出(r^a)^-1 mod p並不難,但我可以用更快方式算出來:
Euler's theorem說: 如果n是質數, Zn 空間與n互質的個數phi(n) = n-1個
a^phi(n) = 1 mod n , 且GCD(a, n)= 1, 將 phi(n) 用 n-1 替換就得到:
a^(n-1) = 1 mod n, 其中 n 是質數
相同來看 r^p-1 ≡ 1 mod p , 其中 p 是質數, gcd(r,p)=1
(r^a)*(r^-a) mod p = 1 mod p = r^(p-1) mod p
r^(a + -a ) mod p = 1 mod p = r^(p-1) mod p
(a)+(-a) = p-1 --> 就可以很簡單推導出
(-a) = p - 1 - a --- (5)
6. 範例:選一個質數p=809,p-1=808=8*101,q=101,
(a) 計算 order=q=101的generator g=16 ???
(b) Alice 選擇密鑰 a =68, 計算 h = g^a mod p = 16^68 mod 809 = 46
(c) (p,g,h) = (809, 16, 46) 傳給 Bob, 密鑰a=68要保密
(d) Bob將明文m=100,選擇亂數k=89加密成:
r = g^k mod p=16^89 mod 809 = 342
s = m * h^k mod p = 100 * 46^89 mod 809 = 745
(f) Alice 收到r=342, s=745,
要計算 s*r^(-a) mod p 先計算出 r^(-a) mod p, a=68, p=809,
而 (-a) = p -1 -a = 809 -1 -68 = 740
而 s=745, r = 342
最後 s * r^(-a) mod p = 745 * 342^740 mod p = 100 mod p
13 術語:
multiplicative group Zp*
Zp* 是刪除無 modulus inverse 的整數空間群組,也就是說裏面的整數元素與p全都互質
例如 Z3的整數空間集合元素共有4 個 = {0,1,2,3}但 Z3* = {1,2}
當 p 是質數時 Zp = {0} | Zp* , Zp* ={1,2,3,...,p-1}
order: 集合順序
例如 |Z3| = 4 , 但 |Z3*|=2
當元素可以分解成質數的乘積時 Z = a^n * b^p * c^q ...
|Zp*| = ( a^n - a^n-1) * (b^p - b^p-1) * (c^q - c^q-1)
例如 6 = 2 *3, Zp={ 0 ,1 ,2, 3, 4, 5} =6
|Zp*| = (2-1) * (3-1) = 1*2=2 ={1,5}
當元素是質數時 |Zp*| = p -1 = phi(p)
映射到指數空間並取餘數:令 Z11*={1,2,3,4,5,6,7,8,9,10}, f(a) = a^Zp* mod 11
令 a = 2
a^1 mod 11 = 2
a^2 mod 11 = 4
a^3 mod 11 = 8
a^4 mod 11 = 5
a^5 mod 11 = 10
a^6 mod 11 = 9
a^7 mod 11 = 7
a^8 mod 11 = 3
a^9 mod 11 = 6
a^10 mod 11 = 1
a^11 mod 11 = 2
ord(2) = 10 個順序: 當 2^k mod 11 =1 時,最小的整數 k=10 就是 order
primitive element:generator
cyclic group: 當group裏面包含有最大 order 的元素時稱之為 cyclic group,該元素就稱為generator,例如 2^i 就可以產生 10 個元素, 最大order元素也包含在內,因此 2是 generator.
當 a 屬於 cycle group時 a^|Zp*| = 1 且 ord(a) 可以被 |Zp*|整除
費曼定理 a^p mod p = a mod p -> a^(p-1) = 1 mod p
p-1 = |Zp*| --> a^|Zp*| =1
ord(1) =1
ord(2) = 10 --> generator
ord(3) = 5
ord(4) = 5
ord(5) =5
ord(6) = 10 --> generator
ord(7) = 10 --> generator
ord(8) = 10 --> generator
ord(9) = 5
ord(10) = 2
可能的 order ={1,2,5,10} 必定可以被 k = 10 整除
Z47* 當 a=5 時 |Z47*|=46, 因此 5 在Z47是 generator
cyclic group 可以產生漂亮的 DPL, 而 generator 可以產生所有的元素.
// 有趣的演算法: Double and Add 及 Square And Multiply
int testBit(int a, int b) {
if( a& (1 << b) ) return 1;
else return 0;;
}
main()
{
int i, b;
int n;
int a=0xa2;
int k;
int e,p,c;
// double-and-add DAA algorithm
b=0;
for( k=8; k>0 ;k-- ) {
if( testBit(a,k) ) {
b=1; // generator
break;
}
}
while( k-- ) {
b += b; // double
if( testBit(a,k) ) b++; // add
}
// square-and-multiply SAM algorithm e^p
e=5;
p=3;
for( k=8; k>0 ;k-- ) {
if( testBit(p,k) ) {
c = e; // generator
break;
}
}
while( k-- ) {
c *= c; // square
if( testBit(p,k) ) c *= e; // multiply
}
printf("a=%d b=%d\n",a,b);
printf("%d^%d=%d\n",e,p,c);
}
5. 求出 d = e^-1 mod phi(33)
因為 phi(33) = 20 , e=3
而 (3*7) mod 20 =1
所以 d = 7 6. (33,3)就是公鑰,7就是私鑰,伺服器將(33,3)傳給使用者要求使用在指數空間編碼,例如將整數a用a^e mod n 來編碼,以a=4為例,公鑰e=4,n=33:
4^3 mod 33 = 64 mod 33 = 31
將4編碼成31,傳回伺服器
7.伺服器同樣使用指數解碼,但改用d來解碼,指數d=7,n=33
31^7 mod 33 = (-2)^7 mod 33 = -128 mod 33 = -4*33+4 mod 33
= 4 mod 33 --> 解碼等於 4,正好就是使用者傳的資料!
8.Euler's theorem:
其中 gcd(a,n)=1如果p是質數,與p互質(coprime)的個數1..p-1全與p互質=phi(p)= p-1,
因此 a^(phi(p))=a^(p-1) = 1 mod p,兩邊同乘以 a
a^p = a mod p
上式就是Fermat's little theorem定理:當p是質數時對任何整數a而言
a^p=a mod p
9.來看編碼/解碼程序中 e,d,n,phi(n)關係:
指數e,d是由phi(n)整數空間推導出來,因為gcd(e,phi(n))=1,因此d必定存在,且互為倒數,換句話說:
e*d = 1 mod phi(n) => ed=1+phi(n)*k, k 是整數
而 a^(ed) = a^(1+phi(n)*k)= a * a^(phi(n)*k)
上述尤拉定理 a^phi(n) = 1 mod n,將上式映射到 mod n 空間就會得到:
a^ed mod n = a * a^(phi(n)*k) mod n = a *1^k mod n = a mod n
詳細參考:https://zh.wikipedia.org/wiki/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
- 將一個整數應映射到指數空間,加密時使用指數e:
y= f(a) = a^e mod n
解密時使用同樣的函數映射到指數空間,但改用指數d:
c=f(y) = y^d mod n = a^(e*d) mod n = a mod n
- 有點要注意的是尤拉定理有個條件 gcd(a,n)=1 才會成立,而n=p*q是兩個質數乘積,只有當a=p或q兩點時會讓gcd(a,n)!=1,因此幾乎可以說a^phi(n)=1 mod n 是成立的除了 a=p, 及 a=q 之外.如果再將 a=p,a=q 單獨處理證明
- p^(ed) mod n = p 且 q^(ed) mod n = q 就可
Alice 選擇私鑰 a, 計算公鑰 Pa = r^a mod n, 並將 Pa 傳給 Bob
Bob 選擇私鑰 b, 計算公鑰 Pb = r^b mod n, 並將 Pb 傳給 Alice
兩人收到後再用私鑰用同樣函式計算出 key
Alice 收到 r^b mod n 計算出 (r^b)^a mod n = r^(ba) mod n
Bob 收到 r^a mod n 計算出 (r^a)^b mod n = r^(ab) mod n
之後使用 a*b 來當 key 加密之後要傳輸的資料
11 這樣資料密鑰交換有沒問題呢? 如果駭客監聽到 Pa 或 Pb,而且他也知道r及n,想要破解a或b
Pa = r^a mod n
Pb = r^b mod n
兩條方程式2個變數(a,b),因為對稱的關係,一條方程式各有一個變數,看似好像有解,但是很難解
單純看一個方程式就好,因為它是mod n的運算關係式,已知 p, r, n想要求出 a,也就是說:
p = r^a mod n --- (1)
因為 p 是餘數,且包含r,a,n等全都是整數,因此可以假設另一個整數k可以讓下列關係式成立:
r^a = p + k*n --- (2)
上式經 mod n 運算後, 最後一項(k*n)會被消去成0,就等同 r^a mod n = p,因為係數全都是整數的關係,如果想要解方程式可以利用嘗試錯誤法勉強可以將上式(1)湊出答案.也就是說讓a從 1, 2,3 ... 一直不停的帶進方程式裏面,再求出兩邊的答案,當兩邊等式成立時就找到答案了.但萬一a,p,n及r都是很大的一個整數的話,比如說 1024 位元組的一個數字,大約是2^1024 次方數量級的一個大整數的話,可是要花費很長一段時間的.
12 ElGamal 加解密演匴法:
1.Alice選一個質數=p及產生器=g,並挑選私鑰=a {2,3,...,p-2},用指數函數計算出h,公鑰就是(p,g,h)可以公開傳給Bob:
h = g^a mod p --- (1)
2.Bob利用Alice傳來的公鑰(p,g,h)將明文m加密,但他先隨機挑選一個亂數:
k 條件式: 滿足1 < k < p-1 且 gcd(k,p-1)=1
也就是說k與p-1必需互質無公因數.同樣使用指數函數計算,並將明文m編碼成(r,s)兩個數傳回給Alice:
r = g^k mod p --- (2)
s = m * h^k mod p --- (3)
3. Alice收到Bob所傳來的的(r,s)後,用私鑰a並用公式計算就可解碼:
m ≡ s * (r^−a) mod p --- (4)
(-a) = p - 1 - a (5)
4. 理由是將(2),(3)式將帶入(4)式就可一窺之迷:
(4) (2) (3)
s * r^-a mod p = m * h^k * (g^k)^-a mod p, 再把(1)式 h = g^a 帶入
= m * (g^a )^k * (g^k)^-a mod p 可以看到後面兩項互相消去了,得到明文 m
= m mod p
5. 在第4式中有一個難題是 r^-a mod p = (r^a)^-1 mod p 是什麼? 它就是指數r^a的模p倒數.當r,a,p已知,因為 p 是質數,要求出(r^a)^-1 mod p並不難,但我可以用更快方式算出來:
Euler's theorem說: 如果n是質數, Zn 空間與n互質的個數phi(n) = n-1個
a^phi(n) = 1 mod n , 且GCD(a, n)= 1, 將 phi(n) 用 n-1 替換就得到:
a^(n-1) = 1 mod n, 其中 n 是質數
相同來看 r^p-1 ≡ 1 mod p , 其中 p 是質數, gcd(r,p)=1
(r^a)*(r^-a) mod p = 1 mod p = r^(p-1) mod p
r^(a + -a ) mod p = 1 mod p = r^(p-1) mod p
(a)+(-a) = p-1 --> 就可以很簡單推導出
(-a) = p - 1 - a --- (5)
6. 範例:選一個質數p=809,p-1=808=8*101,q=101,
(a) 計算 order=q=101的generator g=16 ???
(b) Alice 選擇密鑰 a =68, 計算 h = g^a mod p = 16^68 mod 809 = 46
(c) (p,g,h) = (809, 16, 46) 傳給 Bob, 密鑰a=68要保密
(d) Bob將明文m=100,選擇亂數k=89加密成:
r = g^k mod p=16^89 mod 809 = 342
s = m * h^k mod p = 100 * 46^89 mod 809 = 745
(f) Alice 收到r=342, s=745,
要計算 s*r^(-a) mod p 先計算出 r^(-a) mod p, a=68, p=809,
而 (-a) = p -1 -a = 809 -1 -68 = 740
而 s=745, r = 342
最後 s * r^(-a) mod p = 745 * 342^740 mod p = 100 mod p
13 術語:
multiplicative group Zp*
Zp* 是刪除無 modulus inverse 的整數空間群組,也就是說裏面的整數元素與p全都互質
例如 Z3的整數空間集合元素共有4 個 = {0,1,2,3}但 Z3* = {1,2}
當 p 是質數時 Zp = {0} | Zp* , Zp* ={1,2,3,...,p-1}
order: 集合順序
例如 |Z3| = 4 , 但 |Z3*|=2
當元素可以分解成質數的乘積時 Z = a^n * b^p * c^q ...
|Zp*| = ( a^n - a^n-1) * (b^p - b^p-1) * (c^q - c^q-1)
例如 6 = 2 *3, Zp={ 0 ,1 ,2, 3, 4, 5} =6
|Zp*| = (2-1) * (3-1) = 1*2=2 ={1,5}
當元素是質數時 |Zp*| = p -1 = phi(p)
映射到指數空間並取餘數:令 Z11*={1,2,3,4,5,6,7,8,9,10}, f(a) = a^Zp* mod 11
令 a = 2
a^1 mod 11 = 2
a^2 mod 11 = 4
a^3 mod 11 = 8
a^4 mod 11 = 5
a^5 mod 11 = 10
a^6 mod 11 = 9
a^7 mod 11 = 7
a^8 mod 11 = 3
a^9 mod 11 = 6
a^10 mod 11 = 1
a^11 mod 11 = 2
ord(2) = 10 個順序: 當 2^k mod 11 =1 時,最小的整數 k=10 就是 order
primitive element:generator
ord(1) =1
ord(2) = 10 --> generator
ord(3) = 5
ord(4) = 5
ord(5) =5
ord(6) = 10 --> generator
ord(7) = 10 --> generator
ord(8) = 10 --> generator
ord(9) = 5
ord(10) = 2
可能的 order ={1,2,5,10} 必定可以被 k = 10 整除
Z47* 當 a=5 時 |Z47*|=46, 因此 5 在Z47是 generator
cyclic group 可以產生漂亮的 DPL, 而 generator 可以產生所有的元素.
// 有趣的演算法: Double and Add 及 Square And Multiply
int testBit(int a, int b) {
if( a& (1 << b) ) return 1;
else return 0;;
}
main()
{
int i, b;
int n;
int a=0xa2;
int k;
int e,p,c;
// double-and-add DAA algorithm
b=0;
for( k=8; k>0 ;k-- ) {
if( testBit(a,k) ) {
b=1; // generator
break;
}
}
while( k-- ) {
b += b; // double
if( testBit(a,k) ) b++; // add
}
// square-and-multiply SAM algorithm e^p
e=5;
p=3;
for( k=8; k>0 ;k-- ) {
if( testBit(p,k) ) {
c = e; // generator
break;
}
}
while( k-- ) {
c *= c; // square
if( testBit(p,k) ) c *= e; // multiply
}
printf("a=%d b=%d\n",a,b);
printf("%d^%d=%d\n",e,p,c);
}
沒有留言:
張貼留言