密码学的数学基础1-素数和RSA加密

数学公式推导是密码学的基础, 故开一个新的课题 – 密码学的数学基础系列

素数 / 质数

质数又称素数。 一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）

素数在公钥密码学中的作用？

用于密钥生成，选取一定长度（512 bit）的素数p和q，计算$N=p\ast q$

• 代码片段 - 判断一个数是不是质数(素数)

公钥密码

RSA (基于大整数质数分解的困难问题)

RSA本身就是建立在分解两个大素数乘积的困难性上。两个大素数，相乘非常容易，也非常快，要分解这个乘积却是极为困难。

RSA算法的安全性是由因式分解的困难程度而定的。如果能够找出因式分解那么破解RSA将很容易。
RSA的建议。两个大质数p和q, $p\ast 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)\cdot E(m_2))=m_1+m_2$

支持加法同态, 乘法其实也是变相的加法:
$D(E(m_1{)}^{E(m_2)})=m_1\ast 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系列