sudo apt-get update
sudo apt-get install libssl-dev
2. 開始寫程式, 需引入標頭檔 openssl/rsa.h
#include
#include <openssl/rsa.h>
#include
main(){
int keylen, enclen, declen,i;
char enc[256],dec[256];
char *b="1234";
RSA *key=NULL;
key=RSA_generate_key(2048,RSA_F4,NULL,NULL);
// ...
enclen=RSA_public_encrypt(strlen(b),b,enc,key,RSA_PKCS1_PADDING); declen=RSA_private_decrypt(enclen,enc,dec,key,RSA_PKCS1_PADDING);
keylen=RSA_size(key);
printf("keylen=%d\n",keylen);
printf("enclen=%d\n",enclen);
printf("declen=%d\n",declen);
for(i=0;i<declen;i++) printf("%c",dec[i]);
printf("\n");
RSA_free(key);
}
3. 然後用 gcc
# 可以直接聯結程式庫 ssl 及 crypto, 編譯成可執行檔
gcc rsademo.c -lssl -lcrypto -o rsademo
# 或者透過 pkg-config來產生程式庫連結, 將原始碼編譯成可執行檔
gcc rsademo.c $(pkg-config --libs libssl openssl) -o rsademo
4. 最後執行 rsademo
./rsademo
後記:
1. 觀察解碼後的長度, 如果看到的比原字串長度多 1, 可能是 EOS (end of string)也被編/解碼的關係.
3. 編解碼輸入的長度(bytes 數)最長不可超過 key 所用的長度(bytes 數), 如果超過, 應該分段編碼(例如對於 2048 bits 編碼, 可以每 256 個為一個區塊),
4. RSA 編解碼困難點在於超大整數次方及模數的運算, 一段文碼(例如 2048 bits)將它的指數取 e 或 d 次方, 將會形成超級無敵非比尋常更大的整數, 之後再執行一個超大整數的除法運算最後再取餘數而得出暗碼或明碼. e 一般稱作公鑰指數(public exponent), 而 d 稱為私鑰指數(private exponent), 而 n 就稱為模數, 另外要注意一點是將原文 m 編碼時, 必須讓 m 小於n 否則會出錯, 通常將最高位元組設為 0 就可以辦到.
5. 產生 1024 bits 以下的 RSA 公私鑰, 來未有可能會被破解, 因此用 2048 bits 會較保險
6. 參考文章:http://www.di-mgt.com.au/rsa_alg.html , 節錄重點:
RSA_F4 = 2^(2^4) + 1 = 65537 = 0x10001
常用來當公鑰指數的 5 個質數分別是{ 3, 5, 17, 257, 65537 }, 他共同特點是只有 2 bit 是 1, 同時也都是奇數, 可以讓指數函數的算術運算量變少, 常用的 RSA_F4 , 它就是一個 prime Fermat number, 另外選擇奇數的好處是可以讓驗證公因數時變得較簡單, 像是 (p mod e) !=1 而不是用 gcd(p-1,e)==1 的函數語法.
最後重要的結論, 簡單闡述了RSA演算法的編/解碼重要 3 個參數 (e,d,n ), (e,n) 是公鑰, 而 (d,n)是私鑰, m 是明文, c 是暗文(用公鑰 e 編碼過), e, d 是次方或稱指數(exponent), n 是模數(modulus), 編解碼是用 power modulus n 運算函數, 實際上 e, d 在power modulus n 運算當中是互為倒數(inverse)的反函數運算, 若 f(f'(x)) =x, 則 f 與 f' 互稱為反函數, 正如同 * 與 / 互為倒數運算是一樣的道理, 也就是說當編碼後再用反函數解碼就可以變回原文, 而 pmod(x,e,n) 的反函數正是 pmod(x,d,n) , 因此 pmod( pmod(x,e,n), d,n ) = m = pmod( pmod(x,d,n),e,n )
而為了要找出 d, 參考文章: http://cryptofundamentals.com/rsa
f(x) = pmod(x,e,n) -> f'(x) =pmod(x,d,n)
因此, 將 x 編碼成 c, 再將 c 還原成x 就是說:
c=f(x)=pmod(x,e,n) 且 f'(c)=x=pmod(c,d,n)
或是說, 將 pmod 換成實際的 power modulus 運算, 定義 ^ 是次方(power)運算
c= x^e mod n 且 x= c^d mod n
將 c 帶入後面式子, 則
x = (x^e)^d mod n =x^ed mod n = pmod(x, ed, n ) 也就是說對所有的 m 來說:
m^ed=[m^(ed-1)] *m =m mod n 都要成立
如果說 ed-1 是 n-1 的倍數的話那麼
ed-1=h * (n-1)
m^(ed-1) =m^( h(n-1) ) =m^((n-1)h)
如果 n 是質數, 應用費曼定理可知 m^(n-1)=1 mod n
費曼定理: gp-1 = 1 (mod p) 對於所有的質數 p 來說, 所有非 p 整數倍的數 g, 該方程式都成立,因此:
med - 1 = m(n - 1)h = (mn - 1)h = 1h (mod n)
對於兩個大的質數 p, q , 為了要滿足
m^(ed-1)=m mod p 且 m^(ed-1) = m mod q ---> 這句話不能理解 ???
我們可以令 n=p*q, 也就是說將 n 分解成兩個質數, 利用 Extended Eclidean 演算法找出 d, 讓 ed-1 是 (p-1)*(q-1) 的倍數就可, 也就是說, 如此的話
m^(ed-1) = m^( h*phi ) , phi=(p-1)*(q-1)
當我們將上述方程式, 帶入 mod phi 運算時, 可以知道因為 p, q 是質數的關係, 一定會滿足費曼定理. 讓 m^(h*(p-1)&(q-1)) mod (p-1)*(q-1) 等於 1
ed =1 mod (p-1)*(q-1)
他的條件就是在 power modulus n 的運算下, 為了滿足所有 x, 必須讓指數 e*d=1 mod n 運算之下才會成立, 因就可以找出 d, 而 d 大於 1但小於 phi=(p-1)*(q-1), 因此讓 d 在 2 .. phi 之間測試 e*d=1 mod phi 就可以找到. 但因為 e, d , phi 是大整數, 所要花的時間就會隨 d 及 phi 的數量級而加大, 這個找出 d 的運算函數就叫 inverse modulus.
m = (me mod n)d mod n = (md mod n)e mod n
最後文章提到的 RSA 它的演算法也節錄下來:
keylen=RSA_size(key);
printf("keylen=%d\n",keylen);
printf("enclen=%d\n",enclen);
printf("declen=%d\n",declen);
for(i=0;i<declen;i++) printf("%c",dec[i]);
printf("\n");
}
3. 然後用 gcc
# 可以直接聯結程式庫 ssl 及 crypto, 編譯成可執行檔
gcc rsademo.c -lssl -lcrypto -o rsademo
# 或者透過 pkg-config來產生程式庫連結, 將原始碼編譯成可執行檔
gcc rsademo.c $(pkg-config --libs libssl openssl) -o rsademo
4. 最後執行 rsademo
./rsademo
3. 編解碼輸入的長度(bytes 數)最長不可超過 key 所用的長度(bytes 數), 如果超過, 應該分段編碼(例如對於 2048 bits 編碼, 可以每 256 個為一個區塊),
4. RSA 編解碼困難點在於超大整數次方及模數的運算, 一段文碼(例如 2048 bits)將它的指數取 e 或 d 次方, 將會形成超級無敵非比尋常更大的整數, 之後再執行一個超大整數的除法運算最後再取餘數而得出暗碼或明碼. e 一般稱作公鑰指數(public exponent), 而 d 稱為私鑰指數(private exponent), 而 n 就稱為模數, 另外要注意一點是將原文 m 編碼時, 必須讓 m 小於n 否則會出錯, 通常將最高位元組設為 0 就可以辦到.
5. 產生 1024 bits 以下的 RSA 公私鑰, 來未有可能會被破解, 因此用 2048 bits 會較保險
6. 參考文章:http://www.di-mgt.com.au/rsa_alg.html , 節錄重點:
RSA_F4 = 2^(2^4) + 1 = 65537 = 0x10001
常用來當公鑰指數的 5 個質數分別是{ 3, 5, 17, 257, 65537 }, 他共同特點是只有 2 bit 是 1, 同時也都是奇數, 可以讓指數函數的算術運算量變少, 常用的 RSA_F4 , 它就是一個 prime Fermat number, 另外選擇奇數的好處是可以讓驗證公因數時變得較簡單, 像是 (p mod e) !=1 而不是用 gcd(p-1,e)==1 的函數語法.
而為了要找出 d, 參考文章: http://cryptofundamentals.com/rsa
f(x) = pmod(x,e,n) -> f'(x) =pmod(x,d,n)
因此, 將 x 編碼成 c, 再將 c 還原成x 就是說:
c=f(x)=pmod(x,e,n) 且 f'(c)=x=pmod(c,d,n)
或是說, 將 pmod 換成實際的 power modulus 運算, 定義 ^ 是次方(power)運算
c= x^e mod n 且 x= c^d mod n
將 c 帶入後面式子, 則
x = (x^e)^d mod n =x^ed mod n = pmod(x, ed, n ) 也就是說對所有的 m 來說:
m^ed=[m^(ed-1)] *m =m mod n 都要成立
如果說 ed-1 是 n-1 的倍數的話那麼
ed-1=h * (n-1)
m^(ed-1) =m^( h(n-1) ) =m^((n-1)h)
對於兩個大的質數 p, q , 為了要滿足
m^(ed-1)=m mod p 且 m^(ed-1) = m mod q ---> 這句話不能理解 ???
我們可以令 n=p*q, 也就是說將 n 分解成兩個質數, 利用 Extended Eclidean 演算法找出 d, 讓 ed-1 是 (p-1)*(q-1) 的倍數就可, 也就是說, 如此的話
m^(ed-1) = m^( h*phi ) , phi=(p-1)*(q-1)
ed =1 mod (p-1)*(q-1)
他的條件就是在 power modulus n 的運算下, 為了滿足所有 x, 必須讓指數 e*d=1 mod n 運算之下才會成立, 因就可以找出 d, 而 d 大於 1但小於 phi=(p-1)*(q-1), 因此讓 d 在 2 .. phi 之間測試 e*d=1 mod phi 就可以找到. 但因為 e, d , phi 是大整數, 所要花的時間就會隨 d 及 phi 的數量級而加大, 這個找出 d 的運算函數就叫 inverse modulus.
最後文章提到的 RSA 它的演算法也節錄下來:
- n = pq, where p and q are distinct primes.
- phi, φ = (p-1)(q-1)
- e < n such that gcd(e, phi)=1
- d = e-1 mod phi.
- c = me mod n, 1
- m = cd mod n.
7. 參考以下兩篇文章, 因 bc 可以處理大整數運算, 我們用 bc 語法寫一段小程式來驗證,任取兩個質數 2213, 2663 以及一般常用的公鑰 e =RSA_F4 = 65537 為例
http://www.codedata.com.tw/social-coding/rsa-c-implementation/
https://www.vidarholen.net/contents/blog/?p=24
#!/usr/bin/bc
# bc0.txt for bc script
define pmod(b,e,n) { if(e == 0 ) return 1; if(e == 1) return b%n; rest=pmod(b^2%n,e/2,n); if((e%2) == 1) return (b*rest)%n else return rest; }
define modinv(e,phi) { for(d=2;d<phi;d++ ) if( ((e*d)%phi )==1 ) return d; }
e=65537
p=2213
p=2213
q=2663
n=p*q
phi=(p-1)*(q-1)
d=modinv(e,phi)
m=3320
c=pmod(m,e,n)
b=pmod(c,d,n)
c
b
quit
將上述文字檔改成可執行檔, 交給 bc 執行
chmod 755 bc0.txt
./bc0.txt
或是用 pipe 方式餵給 bc 都可以看出編解碼的結果
cat bc0.txt | bc
以下是輸出結果, 由最後一行可知 b=3320 , 它等於原文 m=3320, 演算法看來是正確的
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
880575
3320
以下是輸出結果, 由最後一行可知 b=3320 , 它等於原文 m=3320, 演算法看來是正確的
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
880575
3320
8. 使用 openssl 工具產生 private key 時若遇到 'unable to write 'random state' 警告訊息時, 極有可能是家目錄下的 .rnd 檔案( ~/.rnd ) 所有權是 root, 用 sudo rm -f ~/.rnd 將它刪除就可以了.
9. 參考文章: https://www.vidarholen.net/contents/blog/?p=24
使用openssl 工具可產生2048 bits 私鑰密碼檔:
openssl genrsa -out private.pem 2048
使用openssl 工具可以秀出 private key 的內容:
openssl rsa -text -in private.pem -noout
其中 modulus 就是 n
publicExponent 就是 e
privateExponent 就是 d
prime1 就是質數 p
prime2 就是質數 q,
exponent1 是 dp
exponent2 是 dq
coefficient 是 qinv
他們都是 hex 編碼的大整數, 我們可以截錄下來放在一個檔案, 假設檔名設成 bc1.txt
9. 參考文章: https://www.vidarholen.net/contents/blog/?p=24
使用openssl 工具可產生2048 bits 私鑰密碼檔:
openssl genrsa -out private.pem 2048
使用openssl 工具可以秀出 private key 的內容:
openssl rsa -text -in private.pem -noout
其中 modulus 就是 n
publicExponent 就是 e
privateExponent 就是 d
prime1 就是質數 p
prime2 就是質數 q,
exponent1 是 dp
exponent2 是 dq
coefficient 是 qinv
他們都是 hex 編碼的大整數, 我們可以截錄下來放在一個檔案, 假設檔名設成 bc1.txt
00:b9:5f:63:3d:71:db:4d:25:f4:5c:4a:e1:51:68:
88:d4:0b:22:71:b2:f0:0a:bb:f6:1c:67:ca:8c:6b:
f0:44:10:f5:df:0b:b8:da:66:c5:36:27:45:54:67:
90:3a:85:9b:ef:12:72:93:1d:2b:2b:21:91:34:22:
74:48:9d:bc:da:26:ad:55:97:3a:31:78:7f:b9:6a:
32:fe:aa:aa:96:ca:a7:57:ee:aa:d6:fa:41:8c:99:
14:d5:4a:29:b2:8e:aa:d9:01:4d:bb:a0:83:b3:76:
ab:3d:dd:dd:2a:0c:34:cb:33:ea:95:80:63:9f:28:
b9:c2:d3:64:71:48:13:e9:9e:e1:ec:68:c9:9a:58:
12:3e:ea:e0:7f:4a:8b:76:75:b1:45:e8:80:06:f7:
b8:16:40:5f:76:b1:dd:1b:6b:29:ae:7b:ba:c7:6b:
b1:a5:64:43:df:dc:2c:07:9e:37:41:3e:01:14:42:
74:14:ff:04:83:76:a8:62:15:fe:17:2f:e9:a9:2b:
b0:e3:70:1a:cd:6b:88:90:dc:e1:ee:e6:70:93:6b:
9f:bf:fa:2b:d6:9c:08:40:0b:60:a0:72:59:17:d9:
eb:b8:cb:ba:95:bc:e5:cf:f9:6e:15:4b:51:bb:2c:
46:e7:21:80:5b:b8:7f:27:1b:8e:c0:73:8d:9e:3e:
68:41
想辦法在檔案前頭加入 ibase=16及換行符號, 將非數字的符號' :\n" (空白, 帽號, 換行 ...等字元)刪除, 並將小寫 a-f 改成用大寫 A-F 取代,最後頭加入換行符號, 之後再餵給 bc 來讓它解出 10 進位大數數,
{ echo 'ibase=16'; cat bc1.txt|tr -d ' ' | tr -d ':\n ' | tr a-f A-F; echo; } | bc
底下就是它的輸出結果:
23401123825161624750491762697897416491699515070048588881539043884916\
52614404727809769029861203264031498390186435703393639991286183531157\
12785557124600390505679222866777702774446692580862083629674398773226\
16285779332858629766558102331637938506289693092631211043031316873250\
92980542341603836495831764652366744692302703394520273759613507298621\
82930057253749148266690206642103206040566846317435137365132327503637\
04634378460871449128239211577985912753381865425918675766146074271491\
42328690031389528282509796743158462464410463960615431436676313304051\
56067895924160222235603357002674929377044727742368871154241543022564\
08641
超長的一個大數字
88:d4:0b:22:71:b2:f0:0a:bb:f6:1c:67:ca:8c:6b:
f0:44:10:f5:df:0b:b8:da:66:c5:36:27:45:54:67:
90:3a:85:9b:ef:12:72:93:1d:2b:2b:21:91:34:22:
74:48:9d:bc:da:26:ad:55:97:3a:31:78:7f:b9:6a:
32:fe:aa:aa:96:ca:a7:57:ee:aa:d6:fa:41:8c:99:
14:d5:4a:29:b2:8e:aa:d9:01:4d:bb:a0:83:b3:76:
ab:3d:dd:dd:2a:0c:34:cb:33:ea:95:80:63:9f:28:
b9:c2:d3:64:71:48:13:e9:9e:e1:ec:68:c9:9a:58:
12:3e:ea:e0:7f:4a:8b:76:75:b1:45:e8:80:06:f7:
b8:16:40:5f:76:b1:dd:1b:6b:29:ae:7b:ba:c7:6b:
b1:a5:64:43:df:dc:2c:07:9e:37:41:3e:01:14:42:
74:14:ff:04:83:76:a8:62:15:fe:17:2f:e9:a9:2b:
b0:e3:70:1a:cd:6b:88:90:dc:e1:ee:e6:70:93:6b:
9f:bf:fa:2b:d6:9c:08:40:0b:60:a0:72:59:17:d9:
eb:b8:cb:ba:95:bc:e5:cf:f9:6e:15:4b:51:bb:2c:
46:e7:21:80:5b:b8:7f:27:1b:8e:c0:73:8d:9e:3e:
68:41
想辦法在檔案前頭加入 ibase=16及換行符號, 將非數字的符號' :\n" (空白, 帽號, 換行 ...等字元)刪除, 並將小寫 a-f 改成用大寫 A-F 取代,最後頭加入換行符號, 之後再餵給 bc 來讓它解出 10 進位大數數,
{ echo 'ibase=16'; cat bc1.txt|tr -d ' ' | tr -d ':\n ' | tr a-f A-F; echo; } | bc
底下就是它的輸出結果:
23401123825161624750491762697897416491699515070048588881539043884916\
52614404727809769029861203264031498390186435703393639991286183531157\
12785557124600390505679222866777702774446692580862083629674398773226\
16285779332858629766558102331637938506289693092631211043031316873250\
92980542341603836495831764652366744692302703394520273759613507298621\
82930057253749148266690206642103206040566846317435137365132327503637\
04634378460871449128239211577985912753381865425918675766146074271491\
42328690031389528282509796743158462464410463960615431436676313304051\
56067895924160222235603357002674929377044727742368871154241543022564\
08641
超長的一個大數字
沒有留言:
張貼留言