公开密钥密码体制（C语言实现RSA加密算法）

公开密钥密码体制：

公开密钥密码体制的产生主要是因为两个方面的原因，一是由于常规密钥密码体制的密钥分配问题，另一种是由于对和数字签名的需求。

传统的加密方法是加密、解密使用同样的密钥，由发送者和接收者分别保存，在加密和解密时使用，采用这种方法的主要问题是密钥的生成、注入、存储、管理、分发等很复杂，特别是随着用户的增加，密钥的需求量成倍增加。在网络通信中，大量密钥的分配是一个难以解决的问题。

1976年美国斯坦福大学的两名学者迪菲和赫尔曼提出了公开密钥密码体制的概念。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
在公开密钥密码体制中，公开密钥PK是公开信息，而秘密密钥SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然秘密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。
该技术采用”非对称式加密方法，也就是两个不同的密钥来对信息加密和解密。

举个例子吧，单看概念属实看不懂
首先我有两把钥匙，公钥和私钥。我可以把我的公钥给任何一个想给我写信的人，他们写完信之后用我的公钥加密，发给我，然后我用自己的私钥解密。这里要强调的是，只要我的的私钥不泄露，这封信就是安全的，即使落在别人手里，也无法解密。

加密解密原理：

对称加密：又称共享密钥加密，使用同一个密钥对数据进行加密解密。
非对称加密：加密解密使用不同密钥，用公钥加密，私钥解密。

RSA公钥加密体制

RSA公共密码密钥体制是一种使用不同的加密密钥与解密密钥，“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。

在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK 。

正是基于这种理论，1978年出现了著名的RSA算法，它通常是先生成一对RSA密钥，其中之一是保密密钥，由用户保存；另一个为公开密钥，可对外公开，甚至可在网络服务器中注册。为提高保密强度，RSA密钥至少为500位长，一般推荐使用1024位。这就使加密的计算量很大。为减少计算量，在传送信息时，常采用传统加密方法与公开密钥加密方法相结合的方式，即信息采用改进的DES或IDEA对话密钥加密，然后使用RSA密钥加密对话密钥和信息摘要。对方收到信息后，用不同的密钥解密并可核对信息摘要。

分析RSA加密原理

RSA算法的过程

RSA算法用到的数学知识特别多，所以在中间介绍这个算法生成私钥和公钥的过程中会穿插一些数学知识。生成步骤如下：

寻找两个不相同的质数
随意选择两个大的质数p和q，p不等于q，计算N=p*q;

1
2
3

什么是质数?我想可能会有一部分人已经忘记了，定义如下：
除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1该数本身两个正因数]的数）。
比如2，3，5，7这些都是质数，9就不是了，因为3*3=9了

根据欧拉函数获取r
r = φ(N) = φ(p)φ(q) = (p-1)(q-1)。
这里的数学概念就是什么是欧拉函数了，什么是欧拉函数呢？

欧拉函数的定义：
欧拉函数 φ(n)是小于或等于n的正整数中与n互质的数的数目。

互质的定义：
如果两个或两个以上的整数的最大公约数是 1，则称它们为互质
例如：φ(8) = 4，因为1,3,5,7均和8互质。

推导欧拉函数:
（1）如果n = 1, φ(1) = 1；(小于等于1的正整数中唯一和1互质的数就是1本身)；
（2）如果n为质数，φ(n) = n - 1；因为质数和每一个比它小的数字都互质。比如5，比它小的正整数1,2,3,4都和他互质；
(3) 如果n是a的k次幂，则 φ(n) = φ(a^k) = a^k - a^(k-1) = (a-1)a^(k-1)；
(4) 若m,n互质，则φ(mn) = φ(m)φ(n)
证明：设A, B, C是跟m, n, mn互质的数的集，据中国剩余定理(经常看数学典故的童鞋应该了解，剩余定理又叫韩信点兵，也叫孙子定理)，A*B和C可建立双射一一对应)的关系。（或者也可以从初等代数角度给出欧拉函数积性的简单证明） 因此的φ(n)值使用算术基本定理便知。（来自维基百科）

选择一个小于r并与r互质的整数e
选择一个小于r并与r互质的整数e，求得e关于r的模反元素，命名为d（ed = 1(mod r)模反元素存在，当且仅当e与r互质），e我们通常取65537。

1
2
3

模反元素：
如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1。
比如3和5互质，3关于5的模反元素就可能是2，因为3*2-1=5可以被5整除。所以很明显模反元素不止一个，2加减5的整数倍都是3关于5的模反元素{...-3, 2,7,12…} 放在公式里就是3*2 = 1 (mod 5)

上面所提到的欧拉函数用处实际上在于欧拉定理：

欧拉定理：
如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立：
a^φ(n) = 1(mod n)
由此可得：a的φ(n - 1)次方肯定是a关于n的模反元素。
欧拉定理就可以用来证明模反元素必然存在。

由模反元素的定义和欧拉定理我们知道，a的φ(n)次方减去1，可以被n整除。比如，3和5互质，而5的欧拉函数φ(5)等于4，所以3的4次方(81)减去1，可以被5整除（80/5=16）。

小费马定理：
假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
a^(p-1) = 1 (mod p)
这其实是欧拉定理的一个特例。

销毁p和q
此时我们的(N , e)是公钥，(N, d)为私钥，爱丽丝会把公钥(N, e)传给鲍勃，然后将(N, d)自己藏起来。一对公钥和私钥就产生了。

主流加密方法：

不可逆加密
常应用于用户密码
可逆加密
1. 对称加密
  常用于身份证号手机号等敏感信息
  将明文和加密密钥一起经过特殊加密处理，使用密钥只有一个
  优点：算法公开、计算量小、加密速度快、加密效率高
  AES、DES、3DES、Blowfish、IDEA、RC4、RC5、RC6等
2. 2 非对称加密
  常用于签名和认证
  非加密算法需要2密钥：私有密钥和公有密钥
  采用公有密钥加密需采用对应私有密钥解密。反之
  优点：非对称加密与对称加密相比，其安全性更好；
  缺点：非对称加密的缺点是加密和解密花费时间长、速度慢，只适合对少量数据进行加密。
  RSA、DSA（数字签名用）、ECC（移动设备用）、Diffie-Hellman、El Gamal等

防御密码破译手段

严禁使用明文存储
不可逆算法
MD5 sha hmac等
安全机制，防止暴力破解（防止暴力破解）
比如验证码，或几次密码错误账号锁定
要复杂，加盐（防止脱库）
盐：没有固定规律的随机字符串，盐越长越复杂，密码越安全，盐进行持久化保存
例如：
f()为某种加密算法
密文=f(明文密码) –> 密文=f(明文密码+盐) –> 密文=f(明文密码+盐+账号相关信息)
客户端加传输过程加密（防止传输劫取）
传输过程例如https/tls

C语言（或其它主流语言）实现RSA加密和解密算法

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>

#define ACCURACY 5
#define SINGLE_MAX 10000
#define EXPONENT_MAX 1000
#define BUF_SIZE 1024

/**
 * Computes a^b mod c，计算a^b mod c
 */
int modpow(long long a, long long b, int c) {
    int res = 1;
    while(b > 0) {
        /* Need long multiplication else this will overflow...
         必须使用长乘法，否则这将溢出*/
        if(b & 1) {
            res = (res * a) % c;
        }
        b = b >> 1;
        a = (a * a) % c; /* Same deal here */
    }
    return res;
}

/**
 * Computes the Jacobi symbol, (a, n)，计算Jacobi符号（a,n）
 */
int jacobi(int a, int n) {
    int twos, temp;
    int mult = 1;
    while(a > 1 && a != n) {
        a = a % n;
        if(a <= 1 || a == n) break;
        twos = 0;
        while(a % 2 == 0 && ++twos) a /= 2; /* Factor out multiples of 2 ,减去2的倍数*/
        if(twos > 0 && twos % 2 == 1) mult *= (n % 8 == 1 || n % 8 == 7) * 2 - 1;
        if(a <= 1 || a == n) break;
        if(n % 4 != 1 && a % 4 != 1) mult *= -1; /* Coefficient for flipping，翻转系数 */
        temp = a;
        a = n;
        n = temp;
    }
    if(a == 0) return 0;
    else if(a == 1) return mult;
    else return 0; /* a == n => gcd(a, n) != 1 */
}

/**
 * Check whether a is a Euler witness for n，检查a是否为n的欧拉见证 */
int solovayPrime(int a, int n) {
    int x = jacobi(a, n);
    if(x == -1) x = n - 1;
    return x != 0 && modpow(a, (n - 1)/2, n) == x;
}

/**
 * Test if n is probably prime, using accuracy of k (k solovay tests)，用k的精度检查n是否可能是素数 */
int probablePrime(int n, int k) {
    if(n == 2) return 1;
    else if(n % 2 == 0 || n == 1) return 0;
    while(k-- > 0) {
        if(!solovayPrime(rand() % (n - 2) + 2, n)) return 0;
    }
    return 1;
}

/**
 * Find a random (probable) prime between 3 and n - 1在3和（n-1）之间找一个随机素数, this distribution is，
 * nowhere near uniform, see prime gaps
 */
int randPrime(int n) {
    int prime = rand() % n;
    n += n % 2; /* n needs to be even so modulo wrapping preserves oddness */
    prime += 1 - prime % 2;
    while(1) {
        if(probablePrime(prime, ACCURACY)) return prime;
        prime = (prime + 2) % n;
    }
}

/**
 * Compute gcd(a, b)，计算gcd（a,b）
 */
int gcd(int a, int b) {
    int temp;
    while(b != 0) {
        temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

/**
 * Find a random exponent x between 3 and n - 1 such that gcd(x, phi) = 1,在3和n-1之间找到随机指数x，使得gcd(x,phi)=1
 * this distribution is similarly nowhere near uniform,这种分布同样不接近制服
 */
int randExponent(int phi, int n) {
    int e = rand() % n;
    while(1) {
        if(gcd(e, phi) == 1) return e;
        e = (e + 1) % n;
        if(e <= 2) e = 3;
    }
}

/**
 * Compute n^-1 mod m by extended euclidian method，用扩展欧几里得法计算n^-1 mod m
 */
int inverse(int n, int modulus) {
    int a = n, b = modulus;
    int x = 0, y = 1, x0 = 1, y0 = 0, q, temp;
    while(b != 0) {
        q = a / b;
        temp = a % b;
        a = b;
        b = temp;
        temp = x; x = x0 - q * x; x0 = temp;
        temp = y; y = y0 - q * y; y0 = temp;
    }
    if(x0 < 0) x0 += modulus;
    return x0;
}

/**
 * Read the file fd into an array of bytes ready for encryption.将文件fd读入准备加密的字节数组
 * The array will be padded with zeros until it divides the number of数组将填充零，知道它划分每个块加密的字节数
 * bytes encrypted per block. Returns the number of bytes read.返回读取的字节数
 */
int readFile(FILE* fd, char** buffer, int bytes) {
    int len = 0, cap = BUF_SIZE, r;
    char buf[BUF_SIZE];
    *buffer = (char *)malloc(BUF_SIZE * sizeof(char));
    while((r = fread(buf, sizeof(char), BUF_SIZE, fd)) > 0) {
        if(len + r >= cap) {
            cap *= 2;
            *buffer = (char *)realloc(*buffer, cap);
        }
        memcpy(&(*buffer)[len], buf, r);
        len += r;
    }
    /* Pad the last block with zeros to signal end of cryptogram. An additional block is added if there is no room，将最后一个带有零的块插入密码的信号端。 如果没有房间，则增加一个额外的街区 */
    if(len + bytes - len % bytes > cap) *buffer = (char *)realloc(*buffer, len + bytes - len % bytes);
    do {
        (*buffer)[len] = '\0';
        len++;
    }
    while(len % bytes != 0);
    return len;
}

/**
 * Encode the message m using public exponent and modulus, c = m^e mod n使用公共指数和模量对消息m进行编码，c = m^e Mod n
 */
int encode(int m, int e, int n) {
    return modpow(m, e, n);
}

/**
 * Decode cryptogram c using private exponent and public modulus, m = c^d mod n，用私有指数和公共模量解码密码c，m = c^d Mod n
 */
int decode(int c, int d, int n) {
    return modpow(c, d, n);
}

/**
 * Encode the message of given length, using the public key (exponent, modulus)
 * The resulting array will be of size len/bytes, each index being the encryption
 * of "bytes" consecutive characters, given by m = (m1 + m2*128 + m3*128^2 + ..),
 * encoded = m^exponent mod modulus
 * 使用公钥（指数、模数)对给定长度的消息进行编码）
 得到的数组将是大小为len/字节，每个索引是由m=(m1m2*128m3*128^2.)给出的“字节”连续字符的加密，编码=m^指数mod模量
 */
int* encodeMessage(int len, int bytes, char* message, int exponent, int modulus) {
    int *encoded = (int *)malloc((len/bytes) * sizeof(int));
    int x, i, j;
    for(i = 0; i < len; i += bytes) {
        x = 0;
        for(j = 0; j < bytes; j++) x += message[i + j] * (1 << (7 * j));
        encoded[i/bytes] = encode(x, exponent, modulus);
#ifndef MEASURE
        printf("%d ", encoded[i/bytes]);
#endif
    }
    return encoded;
}

/**
 * Decode the cryptogram of given length, using the private key (exponent, modulus)
 * Each encrypted packet should represent "bytes" characters as per encodeMessage.
 * The returned message will be of size len * bytes.
 * 使用私钥（指数、模数)解码给定长度的密码）
 每个加密的数据包应该按照编码消息表示“字节”字符。
 返回的消息大小为len*字节。
 */
int* decodeMessage(int len, int bytes, int* cryptogram, int exponent, int modulus) {
    int *decoded = (int *)malloc(len * bytes * sizeof(int));
    int x, i, j;
    for(i = 0; i < len; i++) {
        x = decode(cryptogram[i], exponent, modulus);
        for(j = 0; j < bytes; j++) {
            decoded[i*bytes + j] = (x >> (7 * j)) % 128;
#ifndef MEASURE
            if(decoded[i*bytes + j] != '\0') printf("%c", decoded[i*bytes + j]);
#endif
        }
    }
    return decoded;
}

/**
 * Main method to demostrate the system. Sets up primes p, q, and proceeds to encode and
 * decode the message given in "text.txt"
 * 系统降级的主要方法。 设置素数p，q，并开始编码和
 *解码“text.txt”中给出的消息；
 */
int main(void) {
    int p, q, n, phi, e, d, bytes, len;
    int *encoded, *decoded;
    char *buffer;
    FILE *f;
    srand(time(NULL));
    while(1) {
        p = 17;//randPrime(SINGLE_MAX);
        printf("生成第一个随机素数, p = %d ... ", p);
       getchar();

        q = 11;//randPrime(SINGLE_MAX);
        printf("生成第二个随机素数, q = %d ... ", q);
        getchar();

        n = p * q;
        printf("计算p和q的乘积n, n = pq = %d ... ", n);
        if(n < 128) {
            printf("Modulus is less than 128, cannot encode single bytes. Trying again ... ");
            getchar();
        }
        else break;
    }
    if(n >> 21) bytes = 3;
    else if(n >> 14) bytes = 2;
    else bytes = 1;
    getchar();

    phi = (p - 1) * (q - 1);
    printf("计算欧拉函数的值phi, phi = %d ... ", phi);
    getchar();

    e = randExponent(phi, EXPONENT_MAX);
    printf("选取一个随机素数e, e = %d...\n获得公钥 (%d, %d) ... ", e, e, n);
    getchar();

    d = inverse(e, phi);
    printf("计算模反元素d, d = %d...\n获得密钥 (%d, %d) ... ", d, d, n);
    getchar();

    printf("打开文件 \"text.txt\" 用于读取信息\n");
    f = fopen("text.txt", "r");
    if(f == NULL) {
        printf("Failed to open file \"text.txt\". Does it exist?\n");
        return EXIT_FAILURE;
    }
    len = readFile(f, &buffer, bytes); /* len will be a multiple of bytes, to send whole chunks伦将是多个字节，以发送整个块 */
    fclose(f);

    printf("文件 \"text.txt\" 读取成功, 读取到%d字节. 以%d字节的字节流编码 ... ", len, bytes);
    getchar();
    printf("加密得密文为：");
    encoded = encodeMessage(len, bytes, buffer, e, n);
    printf("\n编码成功完成 ... ");
    getchar();


    printf("正在解码编码的信息 ... ");
    getchar();
    printf("解码得明文为：");
    decoded = decodeMessage(len/bytes, bytes, encoded, d, n);


    printf("\nRSA算法演示完成!\n");

    free(encoded);
    free(decoded);
    free(buffer);
    return EXIT_SUCCESS;
}