@xjump

RSA是一种非对称加密算法，基于特殊大整数（两素数乘积）的因式分解难题保证安全性。

生成密钥的步骤如下：

1、选择大素数p，q。为最大限度提高安全性，要求p与q的位数相当；

2、计算n ＝ p * q。n称为模，modules，我们通常说的1024位密钥，指的是n为1024位，即128字节；

3、计算欧拉函数 Ø(n) ＝ (p-1) * (q-1)。因为n为两素数p，q之积；

4、选择公钥参数e，与Ø(n) 互素。常用的e有3、17及65537；

5、求私钥参数d，满足 e * d ≡ 1 mod Ø(n) ；

6、公钥为n，e。私钥为n，d。p和q将不参与加解密运算；

公钥(n,e)加密 message -> cipher： c ≡ m ^ e mod n

私钥(n,d)解密 cipher -> message: m ≡ c ^ d mod n

证明很简单，这也是RSA的数学美感所在：

e * d = 1 mod (n)  
    => e * d = 1 mod (p-1)*(q-1) 
    => e * d = 1 mod (p-1), AND e * d = 1 mod (q-1) 
    => m ^ (e * d) = m mod p, AND m ^ (e * d) = m mod q
    => m ^ (e * d) = m mod (p * q)

对于裸签名，原理上就是将上面的m和c调换，使用私钥加密，公钥解密。需要注意的是，PKI中的数字签名并不仅仅是裸签名。

附上一段POC：

#!/usr/bin/env python
# -*- coding: utf-8 -*-  
 
'''
author: xjump.me#gmail.com
reference: 
  http://code.activestate.com/recipes/572196-rsa/
'''

def egcd(a,b):
  # Extended Euclidean Algorithm
  # returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
  u, u1 = 1, 0
  v, v1 = 0, 1
  while b:
    q = a // b
    u, u1 = u1, u - q * u1
    v, v1 = v1, v - q * v1
    a, b = b, a - q * b
  return u, v, a

def modInverse(e,phi_n):  
  return egcd(e,phi_n)[0]%phi_n

def main():
  p = 79
  q = 87
  n = p*q
  phi_n = (p-1)*(q-1)
  e = 19
  d = modInverse(e,phi_n)
  print "p=%d, q=%d, n=%d, e=%d, phi_n=%d, d=%d" % (p,q,n,e,phi_n,d)
  m = 30
  c = (m**e) % n # encrypt by public key (n,e)
  m1 = (c**d) % n # decrypt by private key (n,d) 
  print "message is %d, cipher is %d, cipher decrypt out is %d" % (m, c, m1)
  print "\n================start encryption loops attack."
  save_c = None
  c1 = c
  while True:
    m = c1
    c1 = (m**e) % n
    save_c = m
    print "message is %d, cipher is %d" % (m, c1)
    if c1 == c: 
      print "==================got it! after some encryption loops, m is %d" % (save_c)
      break;

main()