數學公式推導是密碼學的基礎, 故開一個新的課題 – 密碼學的數學基礎系列

素數 / 質數

質數又稱素數。 一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數（規定1既不是質數也不是合數）

素數在公鑰密碼學中的作用？

用于密鑰生成，選取一定長度（512 bit）的素數p和q，計算$N=p?q$

• 代碼片段 - 判斷一個數是不是質數(素數)

公鑰密碼

RSA (基于大整數質數分解的困難問題)

RSA本身就是建立在分解兩個大素數乘積的困難性上。兩個大素數，相乘非常容易，也非常快，要分解這個乘積卻是極為困難。

RSA算法的安全性是由因式分解的困難程度而定的。如果能夠找出因式分解那么破解RSA將很容易。
RSA的建議。兩個大質數p和q, $p?q=N$
p和q的相差比較大。防止對N開平方試探。
p-1和q-1有較大的因子。

橢圓曲線(Elliptic Curve Cryptography, ECC) (基于橢圓曲線上的離散對數問題)

利用的是在橢圓曲線上 乘法運算的逆運算 非常困難 的特性

• 比特幣使用的secp256k1橢圓曲線方程是 $x^2=y^3+7$

• ed25519的橢圓曲線方程: $y^2=x^3+486662x^2+x,modulop=2^{255}?19$

Pailier(基于復合剩余類的困難問題)

是一種用于公鑰加密的概率非對稱算法，基于復合剩余類的困難問題（Composite Degree Residuosity Classes），構造在模數取為 $n^2$ 的剩余類{0,1,2,…,$n^2?1$}上(二次剩余)。滿足加法同態，即密文相乘等于明文相加：$D(E(m_1)?E(m_2))=m_1+m_2$

支持加法同態, 乘法其實也是變相的加法:
$D(E(m_1{)}^{E(m_2)})=m_1?m_2$

FISCO BCOS采用的是paillier加密算法，支持加法同態。paillier的公私鑰兼容主流的RSA加密算法，接入門檻低。同時paillier作為一種輕量級的同態加密算法，計算開銷小易被業務系統接受。因此經過功能性和可用性的權衡，最終選定了paillier算法。

術語

• 最大公約數gcd:輾轉相除法，又稱歐幾里得算法
• 最小公倍數lcm
• 二次剩余：X^2在數論中，特別在同余理論里，一個整數X對另一個整數p的二次剩余，是指x的平方除以p得到的余數

數學工具 SageMath

安裝計算工具

#下載網頁
http://mirror.hust.edu.cn/sagemath/linux/64bit/index.html
#下載連接
wget http://mirror.hust.edu.cn/sagemath/linux/64bit/sage-9.3-Ubuntu_20.04-x86_64.tar.bz2
#解壓
tar -xjf sage-9.3-Ubuntu_20.04-x86_64.tar.bz2#運行
cd SageMath
./sage

---

往期精彩回顧:

區塊鏈知識系列

密碼學系列

零知識證明系列

共識系列

公鏈調研系列

BTC系列

以太坊系列

EOS系列

Filecoin系列

聯盟鏈系列

Fabric系列

智能合約系列

Token系列