阳山做网站,北京有哪些不错的互联网公司,全国学校信息查询官网,私人订制旅游网站建设本文主要是简单高效地讲解RSA算法的基本数学原理以及加解密的步骤#xff0c;算法背景以及设计到的数学证明省略。本文主要参考wikipedia和博文《非对称加密算法–RSA加密原理》。 非对称公钥加密算法可以由下列几步实现#xff1a;
信息接收方产生公钥 p k pk pk与私钥 s k…本文主要是简单高效地讲解RSA算法的基本数学原理以及加解密的步骤算法背景以及设计到的数学证明省略。本文主要参考wikipedia和博文《非对称加密算法–RSA加密原理》。 非对称公钥加密算法可以由下列几步实现
信息接收方产生公钥 p k pk pk与私钥 s k sk sk公钥可以给任何人私钥自己保存信息发送方将要发送的信息 m m m与公钥 p k pk pk一起用特定的加密算法加密即密文 c c c信息接收方接收到密文 c c c与私钥 s k sk sk一起用特定解密算法恢复明文。
可见以上加密算法的关键角色是公钥和私钥的生成以及加解密算法的具体操作。RSA算法就是一种实现上述公钥加密的算法。
欧拉函数
RSA算法设计到欧拉函数相关知识下面进行一些简单定义。对于一个整数 n n n我们用欧拉函数 φ ( n ) \varphi (n) φ(n)来表示小于 n n n并与之互质的正整数。下面给出与欧拉函数相关的2条性质证明忽略记住就好
如果 n n n是质数则 φ ( n ) n − 1 \varphi (n)n-1 φ(n)n−1如果 n n n可以表示成2个互质的数的乘积即 n p × q np\times q np×q那么 φ ( n ) φ ( p ) × φ ( q ) \varphi (n)\varphi (p)\times \varphi (q) φ(n)φ(p)×φ(q)。
欧拉定理变型
欧拉定理为如果 m m m与 n n n互质则 m φ ( n ) k n 1 m^{\varphi(n)}kn1 mφ(n)kn1即模 n n n余1。 等式两边同时取整数 l l l次方并再乘上 m m m得 m l φ ( n ) 1 m ( k n 1 ) l k ′ n m m^{l\varphi(n)1}m(kn1)^lk^{}nm mlφ(n)1m(kn1)lk′nm。可见如果 m n mn mn则有 m l φ ( n ) 1 ( m o d n ) m . m^{l\varphi(n)1}~(mod~n)m. mlφ(n)1 (mod n)m.显然这是一个很好地恢复原数 m m m看做是传输的信息的算法这也为后面RSA的算法提供了思路。
模反元素
根据欧拉定理我们知道 m × m φ ( n ) − 1 k n 1 m\times m^{\varphi(n)-1}kn1 m×mφ(n)−1kn1即对于互质的两个数 e e e和 x x x一定存在他的一个模反元素 d d d满足 e × d ( m o d x ) 1 e\times d~(mod~x)1 e×d (mod x)1。该等式重写为 e d k x 1. edkx1. edkx1.注意为了书写方便本文中不同公式出现的符号 k k k可以是任何不相等的整数。
设计一个能恢复信息 m m m的算法
前面我们通过欧拉定理变型可以恢复信息 m m m结合模反元素的公式我们有 m e d m k x 1 . m^{ed}m^{kx1}. medmkx1.假如我们令 x φ ( n ) x\varphi(n) xφ(n)就有 m e d m l φ ( n ) 1 k n m . m^{ed}m^{l\varphi(n)1}knm. medmlφ(n)1knm.我们也可以将 e e e和 d d d分开等价地写成 第 一 步 c m e ( m o d n ) 第一步cm^e~(mod~n) 第一步cme (mod n)和 第 二 步 m c d ( m o d n ) . 第二步mc^d~(mod~n). 第二步mcd (mod n).这两步就是RSA算法的加密和解密过程 m m m是信息 e e e和 n n n是公钥第一步就是加密得到密文 c c c d d d和 n n n是私钥第二步就是解密恢复信息 m m m。 注意至此我们的理论有个假设前提那就是利用欧拉定理的时候需要信息 m m m与 n n n互质实际上 m m m与 n n n不互质也可以用上述公式详细证明参考博文《RSA 算法流程及证明》。此外还有一个限制就是 e e e与 φ ( n ) \varphi(n) φ(n)互质
RSA算法流程
选择两个质数 p p p和 q q q算出他们的乘积 n p × q np\times q np×q算出对应的欧拉函数 φ ( n ) \varphi(n) φ(n)利用性质 φ ( n ) φ ( p ) × φ ( q ) ( p − 1 ) ( q − 1 ) \varphi(n)\varphi(p)\times \varphi(q)(p-1)(q-1) φ(n)φ(p)×φ(q)(p−1)(q−1)。选择一个 e e e使得 e φ ( n ) e\varphi(n) eφ(n)并且 e e e与 φ ( n ) \varphi(n) φ(n)互质。算出 e e e的一个相对于 φ ( n ) \varphi(n) φ(n)的模反元素 d d d。 ( e , n ) (e,n) (e,n)为公钥 ( d , n ) (d,n) (d,n)为私钥信息明文 m m m长度小于 n n n。加密 c m e ( m o d n ) cm^e~(mod~n) cme (mod n)解密 m c d ( m o d n ) mc^d~(mod~n) mcd (mod n)。
