RSA 编程与实现

密码学 RSA

实验原理

1. RSA 原理
   RSA 是目前最有影响力的公钥加密算法,它能够抵抗到目前为止已知的绝大多数密码攻击,已被
   ISO 推荐为公钥数据加密标准。
   RSA 算法基于一个十分简单的数论事实:将两个大素数相乘十分容易,但那时想要对其乘积进行因
   式分解却极其困难,因此可以将乘积公开作为加密密钥。 RSA 的算法涉及三个参数,n、e、d。
   其中 n 是 p、q 两个大素数的乘积,n 的二进制长度一般大于 1024 比特,e 是公钥对里面的小数(相对 n 小),d 为私钥对里的解密用的大数。

   • 密钥的产生:选取一个两个大素数 p 和 q, fn = (p-1)*(q-1)
   • n = p*q;
   • 选取一个与 fn 互素的数作为公钥 e
   • 利用欧几里得逆运算求出私钥数 d

2. 数学基础

   • 数和互为素数
     任何大于 1 的整数 a 能被因式分解为如下唯一形式:
     a=p1p2...pl(p1,p2,...,pl 为素数)

   • 模运算
     1 [a mod n]×[b mod n] mod n≡(a×b) mod n 2 若 a×b = (a×c) mod n, a 与 n 互素,则
     b = c mod n

   • 费马定理 若p是素数,a与p互素,则
     a^(p-1)≡1 (mod p)

   • 欧拉定理
     欧拉函数 φ(n)表示不大于 n 且与 n 互素的正整数的个数。
     当 n 是素数,φ(n)=n-1。n=p×q,p,q 均为素数时,则 φ(n)= φ(p)φ(q)=(p-1)(q-1)。 对于互素的 a 和 n,有 a^φ(n)≡1(mod n)

   • 欧几里德除法 又名“碾除相除法”用于求两个数的最大公约数和私钥。

3. 用到的函数

   • gcd(a,b)
     用于求取两个大数 a,b 的最大公约数
   • rand(a)
     产生一个 0 至 a 之间的随机数
   • rand(a,b)
     产生一个 b 进制,位数为 a 的随机数
   • nextprime(a)
     计算出大于 a 的最近的一个素数
   • inverse(n,fn)
     计算以 n 为公钥,fn 为大数的私钥(fn = (p-1)*(q-1))
   • pow(n,p,m)
     计算 n^p mod m 的值
   • isprime(n)
     判断 n 是不是素数,若是素数返回true,不是素数返回 false

4. 几个函数的实现

gcd():欧几里得算法

#define swap(a, b) \
    do { typeof(a) __tmp = (a); (a) = (b); (b) = __tmp; } while (0)
Big gcd(Big a, Big b) 
{
    Big r;
    if (a < b) swap(a, b); 
    if (!b) return a;
    while ((r = a % b) != 0) 
    { 
        a = b;
        b = r; 
    }
    return b; 
}

pow():蒙格马利快速幂模算法

Big pow(Big a, Big b, Big m)
{
    Big result = 1;
    Big base = a % m;
    while(b>0)
    {
        if(b – ((b>>1)<<1))
        { 
            //p&1 = p - ((p>>1)<<1) 
            result = (result*base) % m;
        }
        base = (base*base) % m; b >>= 1;
    }
    return result; 
}

isprime():判断是否为素数

bool isPrime(const Big &p, int times=100) 
{
    int i,j;
    Big a,x,tmp;
    if (p==1||(p%2==0)) return false; //快速过滤掉合数,以提高速度
    if (p==2||p==3||p==5||p==7||p==9||p==11||p==13||p==17||p==19) return true;
    for(i=0; i<times; i++) 
    { 
        //times 一般不小于 50 次 a = rand(p);
        if(pow(a,p-1,p) == 1)
        {
            //费马小定理验证
            for(j=0; j<times; j++)
            { 
                x = rand(p);
                tmp = pow(x*x,1,p); //欧拉定理二次验证
                if(x!=1&&tmp==1) 
                return false; //出现不是 1 或 p-1 的解,返回假 
            }
        }else
            return false;//不满足第一次验证返回假
    }
        return true; //如果两次验证都通过,返回真 
}

编程实现

#include "big.h" 
#include <iostream> 
#include <cstdlib>
using namespace std;
Miracl precision(10000,2); //初始化 Big 的初始化栈空间
miracl *mip = &precision; //用于设置输入进制和输出进制的转换
void setKey(Big &n, Big &e, Big &d, int bits) //选出 n,e,d,n 为 bits 位 
{
    int half = bits/2;
    Big p,q,fn,tmp;
    tmp = rand(half,2);//产生 bits/2 位的大数 
    p = nextprime(tmp);
    tmp = rand(half,2); 
    q = nextprime(tmp);
    n = p*q; //公钥和私钥里的大整数
    fn = (p-1)*(q-1);
    do{
        e = rand(16,2);
        e = nextprime(e);//寻找离比 e 大且最近的素数 
        if(gcd(e,fn)==1) //如果 e 和 fn 最大公约数不为 1,继续寻找
        break;
    }while(true); //选取合适的公钥 e
    d = inverse(e,fn); //根据欧几里得逆运算计算出私钥 d   
 }
inline Big RSA_encrypt(const Big &dat, const Big &n, const Big &e)//RSA 加密,明文为 dat 
{
    return pow(dat,e,n); 
}
inline Big RSA_decrypt(const Big &dat, const Big &n, const Big &d)//RSA 解密, 密文为 dat 
{
    return pow(dat,d,n); 
}
int main() 
{
    int bits;
    Big n,e,d; cout<<"请输入公钥大数的位数\n>>>"; cin>>bits;
    setKey(n,e,d,bits);
    cout<<"公钥\n>>>("<<e<<", "<<n<<")"<<endl; cout<<"私钥\n>>>("<<d<<", "<<n<<")"<<endl;
    Big tmp; 
    cout<<"请输入加密数据\n>>>"; 
    cin>>tmp;
    tmp = RSA_encrypt(tmp,n,e); 
    cout<<"加密结果\n>>>"<<tmp<<endl;
    tmp = RSA_decrypt(tmp,n,d); 
    cout<<"解密结果\n>>>"<<tmp<<endl;
    cout<<"\n 退出按\"q\",其他任意键继续\n>>>";
    string a,b="q";
    cin>>a;
    if (a==b) return 0;//用于多次演示,输入 q 退出程序
    else main(); 
    return 0;
}

运行结果

[root@localhost ff]# ./RSA
请输入公钥大数的位数
>>>1024
公钥
>>>(41257, 112749437188253611998976100107245620489501728672049259156901260313601850058193421907841740450846889004645942062214871763669405579502073819831065725811214128894656858108675040768955500564087441802798209910423900455749196816864293707101616969763542707788116701384848302333184516915846968423277918945258942570423)
私钥
>>>(9507605787573849677495645642511755912523366072425512582273541087112995039689141595786931066934007001167395410098784178825553530578755479535406783336093605422975190115399843374451315640261214336739677729525275570598801350594563670548427412860683199461179734806549640298910404178262653356966014349824042149769, 112749437188253611998976100107245620489501728672049259156901260313601850058193421907841740450846889004645942062214871763669405579502073819831065725811214128894656858108675040768955500564087441802798209910423900455749196816864293707101616969763542707788116701384848302333184516915846968423277918945258942570423)
请输入加密数据
>>>123456789
加密结果
>>>108001315182820681942810302560470174779088492733783815451047325937118097868477986821934525847409691136429715444472131848217169902826000930527564110872251115478299089991399950285829640055003138904373367711069420896028497170543049701380509333925594060234305489512490195942923400076747049043848485007805843054130
解密结果
>>>123456789
 退出按"q",其他任意键继续
>>>