Network security — implementation of simple RSA algorithm (C++)

preface

This is one of the assignments in the course, which turns the handwriting process into a program

The title

4. In known RSA algorithm, prime p=5,q=7, modulus n=35, public key E =5, plain text is bed, encryption and decryption of plain text are carried out, and encryption operation of RSA public secret key cryptosystem algorithm is completed manually. The alphanumeric mapping table is as follows:

You can refer to the example to explain the NEW RSA encryption algorithm but does not guarantee that the content of the web page is completely correct, please judge for yourself

Analysis of the problem solving

Encryption and decryption process:

• Design of public and private keys (e,n) and (d,n): according to the requirements of p = 5,q = 7, modulus n = 35, and public key E = 5, f(n) = (p-1)*(q-1)=24, e = 5 and f(n) =24 are interprime, so E meets the requirements.
• The calculation formula of key D: d is d*e ≡1 (mod f(n)), that is, 5*d ≡1 mod 24. The derivation of d value is shown in the following table:

• The public and private keys are obtained:

From the above steps, the public key KU =(e,n)=(5,35), private key KR =(d,n) =(5,35)

• English digitization digitizes the plaintext information and groups two digits per block. Assume that the plain text alphabetic code table is an alphabetical list of values, namely:

Letter | a | b | | d | e | c f | g | h | | | | | k j l I m — — — — — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | — – | | | | 02 03 01 – code value | 04 | 05 06 07 | | | | 08 09 10 11 12 13 | | | | | | n letters | o | | p q | r | s | t | | the | | u v w x | | y | z code value 14 15 16 17 18 | | | | | 19 20, 21 22 23 | | | | | | 24 25 26 | | digital express bed, namely: 02,05,04

• Y=X^e mod n Y1 = 2^5 mod 35 = 32 mod 35 = 32 Y2 = 5^5 mod 35 = 3125 mod 35 = 10 Y3 = 4^5 mod 35 = 1024 mod 35 = 9
• X=Y^d mod n to restore plaintext: X1 = 32^5 mod 35 = 33554432 mod 35 = 2 X2 = 10^5 mod 35 = 100000 mod 35 = 5 X3 = 9^5 mod 35 = 59049 mod 35 = 4 That is, restore plain text to bed.

Run a screenshot

code

/* * * Simple RSA encryption and decryption algorithm *HB * Enter p,q,e */
#include <iostream>
#include<string.h>
using namespace std;
/* * Judge prime */
bool isPrime(int n)
{
    if(n%2= =0)return false;
    for(int i= 2; i<n/2+1; i++)if(n%i==0)return false;

    return true;
}
// Judge the mutual quality
bool isMutuality(int e,int fn)
{
    if(e>fn||e<1)return false;
    if(isPrime(e)&&fn%e! =0)return true;
    for(int i = 2; i<=e; i++)if(e%i==0&&fn%i==0)return false;
    return true;
}
/ / d calculation
int getTheD(int e,int fn)
{
    for(int i=1;; i++)if((e*i)%fn==1)return i;
}
// Digital English
// Lower case
void charToNum(char *str,int *num,int n)
{
    for(int i=0; i<n; i++) num[i]=str[i]-'a'+1;
}
// Convert numbers to English
// Lower case
void numToChar(int *num,char *str,int n)
{

    for(int i=0; i<n; i++) { str[i]=(num[i]+'a'- 1) %256; }}// Modulus exponent n
int fMod(int c,int n,int e)
{
    if(c>n)return 0;
    int temp = c;
    //cout<<" "<<endl;
    //cout<<"c="<<c<<" n="<<n<<" e="<<e<<endl;
    for(int i=1; i<e; i++) { c*=temp; c%=n;// Prevent c from being too large
    }

    return c;

}
int num[100];// The maximum value of a ciphertext array is 100
void RSA(int p,int q,int e,char *str)
{
    int len = strlen(str);

    if(len<=0) return;
    if(! (isPrime(p)&&isPrime(q)))return;/ / not a prime number
    int n = p*q;
    int fn = (p- 1)*(q- 1);
    if(! isMutuality(e,fn))return;// E and FN are not mutual
    int d = getTheD(e,fn);/ / d calculation
    cout<<"Public key"<<"("<<e<<","<<n<<")"<<endl;
    cout<<"Key"<<"("<<d<<","<<n<<")"<<endl;
    charToNum(str,num,len);
    cout<<"Ciphertext array :"<<endl;
    for(int i=0; i<len; i++) { num[i] = fMod(num[i],n,e);cout<<num[i]<<"";
    }

    cout<<endl;



}
//*arrNum specifies the ciphertext array
void DeRSA(int p,int q,int e,int len)
{
    cout<<"\n\n------- Decryption program --------"<<endl;
    cout<<"Array of ciphertext currently to be decrypted :"<<endl;
    for(int i=0; i<len; i++) {cout<<num[i]<<"";
    }
    cout<<"\n";


    if(len<=0) return;
    if(! (isPrime(p)&&isPrime(q)))return;/ / not a prime number
    int n = p*q;
    int fn = (p- 1)*(q- 1);
    if(! isMutuality(e,fn))return;// E and FN are not mutual
    int d = getTheD(e,fn);/ / d calculation
    cout<<"Public key"<<"("<<e<<","<<n<<")"<<endl;
    cout<<"Key"<<"("<<d<<","<<n<<")"<<endl;

    cout<<"Declassified plaintext array :"<<endl;
    for(int i=0; i<len; i++) { num[i] = fMod(num[i],n,d);cout<<num[i]<<"";
    }
    cout<<endl;
    char str[100];
    numToChar(num,str,len);
    cout<<"Declassified text :"<<endl;
    cout<<str<<endl;
}
int main(a)
{
    string strM;
    int p,q,e;

    cout<<"* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
    cout<<"* simple RSA encryption and decryption program *"<<endl;
    cout<<"* Input p,q,e *"<<endl;
    cout<<"* p,q is prime,p*q<32767 *"<<endl;
    cout<<* e and FN =(p-1)*(q-1)<<endl;
    cout<<"* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *"<<endl;
    cout<<"Please enter p:";
    cin>>p;
    while(! isPrime(p))cout<<"P is not prime, please re-enter :".cin>>p;
    cout<<"Please enter q:";
    cin>>q;
    while(! isPrime(q))cout<<"If q is not prime, please re-enter :".cin>>q;
    int fn = (p- 1)*(q- 1);
    cout<<"fn:"<<fn<<endl;
    cout<<"Please enter E :";
    cin>>e;
    while(! isMutuality(e,fn))cout<<"E and FN non-mutual reinput :".cin>>e;
    cout<<"Please enter the plaintext to be encrypted :";
    cin>>strM;

    RSA(p,q,e,(char*)strM.c_str());
    DeRSA(p,q,e,strM.length());
    return 0;
}

Copy the code