RSA 入门密码机制解读


		[cpp]  
/* 
 
数论基础，以模余方程制造密码，求模 mod 的 k 次根，对密码解读...  
RSA解密： 通过知道的 mod，和 k ，然后进行对密码破密.... 
 
*/  
  
#include<iostream>  
#include<cstdio>  
#include<cmath>  
#define manx 500  
using namespace std;  
  
long long oula(long long m){  ////欧拉函数   
    int sum=1;  
    for(long long i=2;i*i<=m;i++){  
        long long flag=0;  
        while(m%i==0){  
            m /= i;  
            flag++;  
        }  
        if(flag) sum *= (long long)pow(i,1.0*(flag-1))*(i-1);  
    }  
    if(m>1) sum *= (m-1);  
    return sum;  
}  
  
long long kzgcd(long long a,long long b,long long &x,long long &y){/// 扩展欧几里得   
    if(!b){  
        x=1,y=0;  
        return a;  
    }  
    long long d = kzgcd(b,a%b,x,y);  
    long long t=y;  
    y=x-a/b*y;  
    x=t;  
    return d;  
}  
  
long long inv(long long a,long long b){ ///求逆元   
    long long x,y;  
    long long flag = kzgcd(a,b,x,y);  
    if(flag!=1) return -1;  
    return (x%b+b)%b;  
}  
  
long long mult(long long a,long long n,long long mod){ ///快速幂   
    if(n==1) return a;  
    long long b=1;  
    while(n>1){  
        if(n%2==0){  
            a=a*a%mod;  
            n /= 2;  
        }  
        else {  
            b=b*a%mod;  
            n--;  
        }  
    }  
    return a*b%mod;  
}  
  
int main(){  
    long long m,k;  
    long long x[manx],y[manx];  
    while(cin>>m>>k){  
        int n;   
        cin>>n;  
        for(int i=1;i<=n;i++)  
            cin>>x[i];   /// 收到的密码信息   
        long long ans=oula(m); /// 求欧拉函数   
        long long val=inv(k,ans);  /// 求 k 的逆元   
        for(int i=1;i<=n;i++){  
            y[i]=mult(x[i],val,m);  /// 快速幂，破密解得信息   
            cout<<y[i]<<endl;  
        }  
    }  
}  
  
/* 
 
7081 1789 3 
5192 2604 4222 
 
163276871 79921 5 
145387828 47164891 152020614 27279275 35356191 
 
*/

补充：综合编程 , 安全编程 ,