Something about RSA
in Network with 0 comment

Something about RSA

in Network with 0 comment

RSA

背景简介

假设某个哥们儿要跟某个姐们儿进行一波秘密通信。为了防止中间消息泄露,老姐给了这位老哥一个箱子和一把锁,叫老哥把要送的消息扔进这个箱子里面然后用缩上然后让送快递的去送。然后箱子到了老姐那里之后老姐用自己的钥匙把自己造的那把打开。
我们把这里面的锁叫做公钥(Public Key),这里以$K_A^+$表示,把能解开这把锁的钥匙叫做私钥(Private Key),这里以$K_A^-$表示。所以每次老哥与老姐通信,都会用老姐给的公钥$K_A^+$去加密自己要给老姐发的消息,然后老姐拿到之后用自己的私钥$K_A^-$去解密密文得到老哥发的明文。
首先,在计算机中,一段消息只是一串比特,即一串01组成的序列,我们可以把这串序列比作看作一个二进制数。举个例子,二进制数1011在10进制中表示10。所以,任何一段消息,我们都可以通过某种编码方式去获得其所对应的二进制串,然后通再将这二进制串与其对应的二进制数的十进制对应。这个过程即将消息映射为一个整数。所以以下我们讨论的RSA消息的加密与解密,实质上是对这个整数的操作。

密钥生成

1) 选择两个大素数$p$和$q$,且$p\neq q$,计算$N=pq$
2) 根据欧拉函数,求$r=\phi(N)=(p-1)(q-1)$
3) 选择一个小于$r$的整数$e$,使得$e$与$r$互质,求$e$关于$r$的模逆元,记为$d$,即求出$d$使得$ed\equiv 1(mod\quad r)$
4) 销毁$p$,$q$.

$(N,e)$作为公钥,即$K_A^+$,也就是姐们儿给哥们儿的那把锁。
$(N,d)$作为私钥,即$K_A^-$,也就是姐们儿自己用来开箱子的那把锁,姐们儿自己会把钥匙藏起来,不让除她之外的任何人知道。

加密

假设哥们儿需要加密的二进制串代表的整数为n,哥们儿用公钥计算
$$c=n^e (mod\quad N)$$
算出来之后就传给姐们儿。

解密

姐们儿拿到了哥们儿传给她的那个加密后的数字$c$,也就是那个二进制串,作以下解密操作
$$n=c^d(mod\quad N)$$
得到哥们儿加密前的那个数$n$。

原理证明

因为$c^d\equiv n^{ed}(mod\quad N)$
而$ed\equiv 1(mod\quad r)$,则$ed=1+hr$,$ed=1+h\phi(N)$
$n^{ed}=n^{1+h\phi(N)}=n\cdot({n^{\phi(N)}})^h$
根据欧拉定理可知$n\cdot({n^{\phi(N)}})^h\equiv n\cdot(1)^h(mod\quad N)\equiv n(mod\quad N)$。
Remark:由于$ed\equiv 1(mod\quad r)$的存在,所以先解密再加密也是可行的。

Responses