常见密码学算法
學習筆記
分類
密碼學用于解決信息安全中的保密性，完整性，認證和不可否認性等問題。最初主要用于解決保密性。隨著密碼學技術的發(fā)展，逐漸應用到其它領域。
常見密碼學算法：DES,AES; RSA, ECC; Hash; Signature等。
分類
- 對稱密碼
- 流密碼
- 分組密碼
- 非對稱密碼
不同階段
古典/經(jīng)典密碼（凱撒密碼），（1949 Shannon）近代密碼（DES/AES），（1976 Diffie-Hellman, 1977 RSA）現(xiàn)代密碼（RSA），（展望：量子密碼等）
參考：
Ref https://mp.weixin.qq.com/s/wiblmEu14iB1yx6g6sTCnw
Ref Wikipedia
Ref 密碼學發(fā)展史（https://github.com/guoshijiang/Cryptography_anyone_can_understand/blob/master/history/README.md）
各類算法
經(jīng)典密碼
凱撒密碼
對稱密碼
加密和解密使用相同的秘鑰。優(yōu)點是加密解密效率高，缺點是秘鑰的分發(fā)需要在隱秘通道進行。安全性取決于根據(jù)密文無法推出明文和秘鑰。
-
基于異或的一次性密碼。（多個密文可以解密出秘鑰）(一次一密密碼被證明是絕對安全的密碼。1949 Shannon）
- 秘鑰大于等于原消息，具備很好的安全性
- 問題是秘鑰長度很大不易分配和管理
-
流密碼。使用偽隨機生成器，根據(jù)初始秘鑰來生成一次性秘鑰。安全性取決于與初始秘鑰的保密性和偽隨機生成器的隨機性（不可預測性）。保密性較一次性密碼弱，但秘鑰容易分配和管理。
使用流密碼要考慮安全性，例如同一個key不能使用兩次：
Stream ciphers, where plaintext bits are combined with a cipher bit stream by an exclusive-or operation (xor), can be very secure if used properly[citation needed]. However, they are vulnerable to attacks if certain precautions are not followed:
keys must never be used twice
valid decryption should never be relied on to indicate authenticity
From https://en.wikipedia.org/wiki/Stream_cipher_attacks
- 分組密碼：加密的明文和輸出的密文長度相同，秘鑰決定了輸入明文和輸出密文的映射關系，且是1對1映射。為了加密任意長度的明文，引入了電子密碼本模式（Electronic codebook, ECB)和分組鏈接模式（Cipher block chaining, CBC)等。例如DES,AES
非對稱密碼
加密和解密使用不同的秘鑰。優(yōu)點是秘鑰分發(fā)和管理更方便，且可以支持簽名等功能。缺點是加密和解密效率低。安全性取決于根據(jù)密文和公鑰無法推出明文和私鑰。
RSA系列
- RSA
- Diffe-Hellman Key exchange
- DSA
ECC系列
- ECIES
- ECDH
- ECDSA
各種算法
RSA
RSA 原理、構建、加解密和大數(shù)分解的安全假設
Ref http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
Ref http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
Ref wikipedia https://en.wikipedia.org/wiki/RSA_Security https://en.wikipedia.org/wiki/RSA
數(shù)學基礎
歐拉函數(shù)
歐拉定理
模逆元
如果ab對n模1
- 則有ab = h*n + 1
- 進一步有 m^ab = m^(hn+1) = m^(hn) * m
RSA構建
- 取兩 個質(zhì)數(shù)p,q,求得n=p*q, 歐拉函數(shù)phi(n)=phi§phi(q)=(p-1)(q-1)
- 取兩個質(zhì)數(shù)方便求解歐拉函數(shù)phi(n)
- 取一個與n互質(zhì)的數(shù)e,求解d使得e*d模phi(n)為1
- ed模phi(n)為1，則有 m^(ed) = m^(hphi(n) + 1) = m^(h*phi(n)) * m 模n的值為m
- (n,e)為公鑰,(n,d)為私鑰，其它數(shù)據(jù)如phi(n), q, p不公開
- RSA的安全性保障在于大整數(shù)因式分解是個難題，已知(n,e)很難求解d使得 e*d模phi(n)的值為1
- 求解d需要phi(n)
- 而求解phi(n)需要p,q
- 而從n求解p,q是個大整數(shù)因式分解問題
- RSA的安全性保障在于大整數(shù)因式分解是個難題，已知(n,e)很難求解d使得 e*d模phi(n)的值為1
RSA加解密
- 密文為m^d mod n
- 明文為m^(d*e) mod n = m^(phi(n)+1) mod n = m ^ phi(n) * m mod n
- 如果m和n互質(zhì)，則明顯明文解密后為m
- 如果m和不互質(zhì)，也可證明明文解密后為m
RSA上的算法有加解密，簽名，秘鑰交換等
RSA的秘鑰長度應該在1024以上，重要場景需要2048
RSA乘法同態(tài)
- A =Enc(a, pk_dn) = a ^d mod n
- B = Enc(b, pk_dn) = b ^d mod n
- A*B = Enc(ab, pk_dn) = (ab)^d mod n = a ^d * b ^d mod n
Diffie-Hellman key exchange
Diffie-Hellman密鑰交換算法
基于離散對數(shù)難問題
p為素數(shù)，假定g是生成器，基于x (1,2,…,p-1)，有n使得x=g^n mod p
- p和g公開
- A: g^a mod p
- B: g^b mod p
- 則A*B = (ga)b mod p = (gb)a mod p
- A + B = g^a + g^b mod p = g^(a+b) mod p
加法同態(tài)
- A = g^a
- B = g^b
- A + B = g^a * g^b = g ^ (a + b)
ECC橢圓曲線密碼學
定義在橢圓曲線上的加法群，其中無窮遠點是單位元O。
- 然后可定義逆元，加法運算，結合律，交換律。
- 幾何定義可參見上面的鏈接。加法的代數(shù)計算見上面鏈接。
- 如何在有限橢圓曲線上構造參數(shù)見上面鏈接
應用:
ECDH, ECDSA
Ref:
https://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/
https://www.jianshu.com/p/3b810faff3ba
ElGamal 加密算法
基于Diffie-Hellman算法,基于離散對數(shù)難問題
https://zh.wikipedia.org/wiki/ElGamal%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95
- Diffie-hellman版本
- ECC版本
算法
- Alice的公鑰和私鑰(a,g^a)
- Bob的公鑰和私鑰(b,g^b)
- Bob對數(shù)據(jù)m的加密數(shù)據(jù)為: 將m映射到曲線上一點，如(m,m_y)，則加密為(g^b, m_y*((g^a)^b))
Difference of pedersen and elgamal
https://crypto.stackexchange.com/questions/11923/difference-between-pedersen-commitment-and-commitment-based-on-elgamal
- Pedersen: gm*hr. No one know the y such that h=g^y.
- Elgamal: g^r, gm*hr. receiver knows the y such that h=g^y.
- If receiver knows the y such as h=g^y, then receiver can get g^m.
○ The main difference is that Pedersen commitments are unconditionally hiding. It will becomes to be computing hiding if - If sender knows the y such as h=g^y, then there is a trapdoor commitment in elgamal.
各種安全假設
http://blog.sciencenet.cn/blog-1362128-1095141.html
- 整數(shù)分解假設
- RSA假設
- 離散對數(shù)假設
數(shù)學基礎
集合論基礎
- 非空集合，滿足封閉性，是廣群；再滿足結合律，是群；有單位元，是幺半群；有逆元是群；再滿足交換律，是阿貝爾群。
- 群。<R,+>表示一個擁有滿足封閉性、滿足結合律、有單位元、有逆元的二元運算的代數(shù)結構，包括阿貝爾群、同態(tài)和共軛類。
- 滿足交換律，則是阿貝爾群
- 環(huán)。<R,+,*)表示一個環(huán)。單位元不同。
- 在+上是一個阿貝爾群
- 在*上滿足結合律，是一個半群
- 對+和*滿足分配律
- 域。設<R，+，* >是環(huán)，如果<R，+>和<R-{0},>都是交換群（“0”為<R,+>的單位元）且滿足分配律，則稱<R，+，>是域。比如：有限整數(shù)環(huán)<R，+，*>是域。
循環(huán)群是—種很重要的群，也是已被完全解決了的—類群。其定義為若—個群G的每—個元都是G的某—個固定元a的乘方，則稱G為循環(huán)群，記作G=(a)，a稱為G的—個生成元。循環(huán)群有無階循環(huán)群和有階循環(huán)群兩種類型。
From https://baike.baidu.com/item/循環(huán)群
Next
- Comparation of ECDH and DH
- Comparation of ECDSA and DSA
- 其它體系https://blog.csdn.net/jingzi123456789/article/details/104761739/
- ElGamal
- 加密數(shù)據(jù)具備乘法同態(tài)
- Paillier
- 加密數(shù)據(jù)具備加法同態(tài)
- ElGamal
總結
- 上一篇： 卷积神经网络模型之——VGG-16网络结
- 下一篇： android上跑脚本,光遇自动跑图脚本