一 欧拉数论定理

1. 欧拉函数

      设n为一正整数，则欧拉函数$\phi (n)$等于$0\sim n-1$中与n互素的整数个数
      比如$\phi (5)=4$，因为0~5中， 1,2,3,4均与5互素，即最大公约数为1

2. 欧拉定理

      设a,n为两个正整数，且(a,n)=1，则有：aφ(n)≡1mod(n)a^{\\varphi (n)} \\equiv 1 \\, mod (n)aφ(n)≡1mod(n)

二 RSA数学原理

      给定两个不同的素数p,q，令n=p*q，则$\phi (n)=(p-1)(q-1)$,对于满足$cd\equiv 1mod(\phi (n))$的两个正整数c,d，显然满足：acd≡amod(n)a^{cd} \\equiv a \\, mod (n)acd≡amod(n)。

(1) 对于明文M，则有密文C=M^e mod n  (获得密文是明文的e次方再模n)    
(2) 对于密文C，则有明文M=C^d mod n  (获得明文是密文的d次方再模n)

      明文和密文的产生是建立在一对密钥的基础上的，即(e,n)和(d,n) 。其中，(e,n)称为公钥 , (d,n)称为私钥。公钥在网络中公开，谁都可以使用；私钥在本地保存，仅限自己使用。根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因而在大素数条件下根据公钥去计算私钥是比较耗时的过程，由此保证了信息的安全。

三 Python实现RSA

import random'''
计算两个整数的最大公因数，采用欧几里得算法，其原理具体描述为：
假设 a = t*b + r ，那么a与b最大公约数等于b与r最大公约数
gcd(a,b) = gcd(b,r)
'''def gcd(a, b):while b != 0:a, b = b, a % breturn a'''
当满足 ab同余1模m 时，b即为 a模m 下的逆，采用欧几里得算法反推计算
A1 = T1*A2 + A3
A2 = T2*A3 + A4
......
An = Tn*A(n+1) + A(n+2)
结束时，A(n+2) = 1
'''def inverse(e, phi):a, b, t = phi, e, 0x, y = 0, 0x1, y1 = 1, 0x2, y2 = 0, 1while (a % b) != 1:t = a // bx, y = x2, y2x2, y2 = x1 - t * x2, y1 - t * y2x1, y1 = x, ya, b = b, a % bt = a // bx, y = x1 - t * x2, y1 - t * y2return (y + ((abs(y)) // phi + 1) * phi) % phi'''
测试所选整数是不是质数
'''def is_prime(num):if num == 2:return Trueif num < 2 or num % 2 == 0:return Falsefor n in range(3, int(num ** 0.5) + 2, 2):if num % n == 0:return Falsereturn True'''
生成公钥和私钥
'''def generate_key_pair(p, q):if not (is_prime(p) and is_prime(q)):raise ValueError('Both numbers must be prime.')elif p == q:raise ValueError('p and q cannot be equal')if p < 11 or q < 11:raise ValueError('p or q should larger than 10')  # 保证n大于128，容纳ASCII字符n = p * qphi = (p - 1) * (q - 1)e = random.randrange(1, phi)g = gcd(e, phi)while g != 1:e = random.randrange(1, phi)g = gcd(e, phi)d = inverse(e, phi)# Public key is (e, n) and private key is (d, n)return ((e, n), (d, n))def encrypt(pk, plaincode):key, n = pkciphercode = [pow(code, key, n) for code in plaincode]return ciphercodedef decrypt(pk, ciphercode):key, n = pkplaincode = [pow(code, key, n) for code in ciphercode]plaintext = [chr(code) for code in plaincode]return ''.join(plaintext)if __name__ == '__main__':'''Detect if the script is being run directly by the user'''print("===========================================================================================================")print("================================== RSA Encryptor / Decrypter ==============================================")print(" ")p = int(input(" - Enter a prime number (11, 13, 17, 19, 23， etc): "))q = int(input(" - Enter another prime number (Not one you entered above): "))print(" - Generating your public / private key-pairs now . . .")public, private = generate_key_pair(p, q)print(" - Your public key is ", public, " and your private key is ", private)message = input(" - Enter a message to encrypt with your public key: ")plaintext = [char for char in message]plaincode = [ord(char) for char in message]print(" - Your plaintext is: ", plaintext, "and your plaincode is: ", plaincode)print(" - Encrypting message with public key ", public, " . . .")ciphercode = encrypt(public, plaincode)ciphertext = [chr(code) for code in ciphercode]print(" - Your ciphertext is: ", ciphertext, "and your ciphercode is: ", ciphercode)print(" - Decrypting message with private key ", private, " . . .")print(" - Your message is: ", decrypt(private, ciphercode))print(" ")print("============================================ END ==========================================================")print("===========================================================================================================")

四 C语言实现RSA

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>
#include <wchar.h>
using namespace std;
// 计算最大公因数
int gcd(long int a, long int b){return b==0?a:gcd(b,a%b);
}
// 计算模phi的逆
int inverse(long int e, long int phi){long int a=phi, b=e, t=0;long int x=0, y=1;while(a%b!=1){t = x;x = y;y = t-y*(a/b);t = a;a = b;b = t%a;}return ((x-y*(a/b))%phi+phi)%phi;
}
//检测是不是质数
int is_prime(long int num){if (num==2) return 1;if (num<2||num%2==0) return 0;long int n = 3;while(1){if (n*n>num) return 1;if (num%n==0) return 0;n += 2;}
}
void generate_key_pair(long int p, long int q, long int* r){if (!(is_prime(p)&&is_prime(q))){printf("Both numbers must be prime.");exit(2);}if (p==q||p+q<24){printf("p and q cannot be equal.");exit(2);}long int n = p * q;long int phi = (p - 1) * (q - 1);srand((unsigned)time(NULL));long int e = (rand()+1)%phi;long int g = gcd(e, phi);while (g != 1){e = (e+rand()+1)%phi;g = gcd(e, phi);}long int d = inverse(e, phi);// Public key is (e, n) and private key is (d, n)r[0] = e;r[1] = n;r[2] = d;r[3] = n;
}
// 指数取模运算
long int ModExp(long int base, long int exp, long int mod){long int res = 1;while(exp){if (exp%2==1) res = (res*base) % mod;exp /= 2;base = (base*base) % mod;//底数平方}return res;
}
void encrypt(long int* pk, long int* plaincode, long int* ciphercode, int length){int key=pk[0], n=pk[1];for (int i=0;i<length;i++) ciphercode[i] = ModExp(plaincode[i],key,n);
}
wstring decrypt(long int* pk, long int* ciphercode, int length){int key=pk[0], n=pk[1];wstring result;long int* plaincode = (long int*)malloc(length*sizeof(long int));for (int i=0;i<length;i++) plaincode[i] = ModExp(ciphercode[i],key,n);for (int i=0;i<length;i++) result = result + wchar_t(plaincode[i]);return result;
}
int main(){printf("===========================================================================================================\\n");printf("================================== RSA Encryptor / Decrypter ==============================================\\n");long int p,q;printf(" - Enter a prime number (11, 13, 17, 19, 23, etc): ");cin >> p;printf(" - Enter another prime number (Not one you entered above): ");cin >> q;long int* key_pairs = (long int*)malloc(4*sizeof(long int));printf(" - Generating your public / private key-pairs now . . .\\n");generate_key_pair(p,q,key_pairs);long int* key_public = (long int*)malloc(2*sizeof(long int));long int* key_private = (long int*)malloc(2*sizeof(long int));key_public[0]=key_pairs[0];key_public[1]=key_pairs[1];key_private[0]=key_pairs[2];key_private[1]=key_pairs[3];printf(" - Your public key is (%ld,%ld) and your private key is (%ld,%ld)\\n",key_public[0],key_public[1],key_private[0],key_private[1]);printf(" - Enter a message to encrypt with your public key: ");wstring message;wcin >> message;int length = message.size();long int* plaincode = (long int*)malloc(length*sizeof(long int));long int* ciphercode = (long int*)malloc(length*sizeof(long int));for (int i=0;i<length;i++) plaincode[i] = message[i];cout << " - Your plaintext is: [";for (int i=0;i<length;i++) wcout << " " << message[i] << " ";cout << "]    and your plaincode is: [";for (int i=0;i<length;i++) cout << " " << plaincode[i] << " ";cout << " ]" << endl;printf(" - Encrypting message with public key (%ld, %ld) . . .\\n", key_public[0], key_public[1]);encrypt(key_public,plaincode,ciphercode,length);cout << " - Your ciphertext is: [";for (int i=0;i<length;i++) wcout << " " << wchar_t(ciphercode[i]) << " ";cout << "]    and your ciphercode is: [";for (int i=0;i<length;i++) cout << " " << ciphercode[i] << " ";cout << " ]" << endl;printf(" - Decrypting message with private key (%ld, %ld) . . .\\n", key_private[0], key_private[1]);wstring ws = decrypt(key_private, ciphercode,length);wcout << " - Your message is: " << ws << endl;printf("============================================ END ==========================================================\\n");printf("===========================================================================================================\\n");return 0;
}