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) & e * d ≡ 1 mod (q-1)

=> m ^ (e * d) ≡ m mod p & 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()