公钥密码与RSA加密

公钥密码体制

一对公钥私钥,一个用于加密,另一个就能用来解密。
攻击者不能通过密文和公钥推出私钥。

对称密码体制的问题

加密主要步骤

  • 每一个用户产生一对密钥,用来加密和解密消息。
  • 每一个用户将其中一个密钥存在公开的环境,作为公钥;另一个密钥保持保密,即作为私钥;一个用户可以拥有其他用户的公钥。
  • 若Bob要发消息给Alice,则Bob用Alice的公钥对消息进行加密。
  • Alice获得之后,用私钥对其解密,由于只有Alice知道自身的私钥,所以其他接收者都不能解密出消息。

认证主要步骤

和加密类似,但是做签名的时候是认证用户先用私钥加密消息,公众用公钥进行解密,若解密成功则表示认证成功。

RSA 算法

Diffie和Hellman尽管提出了公钥加密的思想方法,但是直到Ron Rivest,Adi Shamir和Len Adleman才找到一个合适加密算法。
RSA体制是一种分组密码,其明文和密文都是0至n-1的整数,通常n为1024位的二进制数。

$$\begin{gather}
C = M^e mod \ n \
M = C^d mod \ n = (M^e)^d mod \ n = M^{ed} mode \ n
\end{gather}
$$

公钥$PU= \lbrace e, n \rbrace$,私钥$PR= \lbrace d,n \rbrace$

具体

  • 选择两个素数p,q(保密)
  • 计算$n=pq$(公开)
  • 选择$e$满足$\gcd(\phi (n),e)=1;1 \lt e \lt \phi(n)$(公开)
  • 计算$de \equiv 1 mod \phi (n)$,得到d(保密)

则公钥为{e,n},私钥为{d,n}

CTF 中的 RSA

EasyCTF RSA1

p = 33499881069427614105926941260008415630190853527846401734073924527104092366847259

q = 34311544767652906613104559081988349779622789386528780506962212898921316785995851

e = 65537

c = 43465248299278658712013216049003172427898782261990372316282214376041873514481386908793943532363461126240609464283533882761307749486816342864113338277082746552

这一题中,既然已经知道了p和q,那就意味着直接知道了n,然后就能推出d,自然可以算出m

import libnum

p = 33499881069427614105926941260008415630190853527846401734073924527104092366847259
q = 34311544767652906613104559081988349779622789386528780506962212898921316785995851
e = 65537
c = 43465248299278658712013216049003172427898782261990372316282214376041873514481386908793943532363461126240609464283533882761307749486816342864113338277082746552

phin = (p-1)*(q-1)
d = libnum.invmod(e, phin)
m = pow(c,d,n) # 相当于 pow(c,d)%n
s = hex(m)[2:].rstrip('L')
print s.decode("hex")