encryption : RSA algorithm

Question

I am implementing the RSA algorithm for encryption and decryption as given here:

http://www.di-mgt.com.au/rsa_alg.html

But could not understand the random prime number generation part in key generation. So I am taking two prime numbers as inputs from user. I had difficulties with generating the e also. so I made it constant (e= 17)

Some prime number inputs working properly ( i.e encoding and decoding properly) in gcc under linux but not in devcpp under windows. (e.g 53,61)

Here is the key generation code:

/* Generates private and public keys and saves into two separate files */
void keygen()
{
    int p,q,phi,d,e,n,s;

    printf("\n Enter two prime numbers: ");
    scanf("%d%d",&p,&q);

    n = p*q;
    phi=(p-1)*(q-1);

    e=17;

    // selec d such that d*e = 1+ k*phi for some integer k.
    d = 0;
    do
    {
        d++;
        s = (d*e)%phi;
    }while(s!=1);

    printf("\n public key: { e=%d n=%d }",e,n);
    printf("\n private key: { d=%d n=%d }\n",d,n);

}

Need help and suggestions in the prime number and e generation.

Answer 1

so you already know that e * d needs to be congruent to 1 mod phi(n)

since you know phi(n) a tuple (e,d) can be calculated by using the extended euclidean algorithm (EEA):

choose an integer for e (usually a small integer; this will be the public exponent, encryption will be faster with smaller exponents) that is less than phi(n) and greater than 2 (?... i think)

when you have a candidate for e, calculate the greatest common divisor (gcd) of e and phi(n) ... should be 1 ... if not, choose a new candidate for e and repeat (since there would be no modular inverse, in other words no private exponent d exists for this e and phi(n))

after you know that gcd(e,phi(n))==1 you can calculate d using the EEA (or as a shortcut, calculate EEA directly since it will also provide the GCD ... if that's not 1, choose a new value for e)

EEA (quick and dirty for calculating modular inverse):

imagine a table with 3 columns:

lets say those columns are named: b, q and t

so the lines of that table will look like:

b0, q0, t0
b1, q1, t1
...
(and so on)

the first 2 rows will be initially filled. for all other rows there is an itterative rule that can be applied to the previous two rows that will result in the values for the next row

the first 2 rows are:

phi(n), NO_VALUE, 0
e, floor(phi(n)/e), 1

the itterative rule to create the next row is: (where [] is an index operator for selecting the row)

b[i] = b[i-2] mod b[i-1]
q[i] = b[i-1] / b[i] (integer division, no fractions ... )
t[i] = t[i-2] - ( q[i-1] * t[i-1] )

you can abort the scheme when b[i] becomes 0 or 1 ... you don't really need q for the last row ...

so if b[i] is 0, b[i-1] can not be 1 since you should have aborted when you calculated b[i-1] if that were 1 ...

if you reach b[i]==0, b[i-1] is your gcd ... since it is not 1 you need a new value for e

if b[i]==1 your gcd is 1, and there is an inverse ... and that is t[i] (if t is negative, add phi(n))

example with real values:

let's say phi(n) is 120 let's say we choose 23 as a candidate for e

our table will look like:

b     q     t
120   –     0
23    5     1
5     4     -5
3     1     21
2     1     -26
1     2     47

the last calculated b is 1 so => gcd(23,120) == 1 (proof: the inverse exists)
the last calculated t is 47 => 23*47 mod 120 == 1 (t is the inverse)

Answer 2

Dear Friend just follow this algorithm

 Key generation
1) Pick two large prime numbers p and q, p != q;
2) Calculate n = p × q;
3) Calculate ø (n) = (p − 1)(q − 1);
4) Pick e, so that gcd(e, ø (n)) = 1, 1 < e <  ø (n);
5) Calculate d, so that d · e mod ø (n) = 1, i.e., d is the multiplicative inverse of e in mod  ø (n);
6) Get public key as KU = {e, n};
7) Get private key as KR = {d, n}.
Encryption
For plaintext block P < n, its ciphertext C = P^e (mod n).
Decryption
For ciphertext block C, its plaintext is P = C^d (mod n).

Code:
#include<stdio.h> 
#include<conio.h> 
#include<stdlib.h> 
#include<math.h> 
#include<string.h> 

long int p,q,n,t,flag,e[100],d[100],temp[100],j,m[100],en[100],i; 
char msg[100]; 
int prime(long int); 
void ce(); 
long int cd(long int); 
void encrypt(); 
void decrypt(); 
void main() 
{ 
clrscr(); 
printf("\nENTER FIRST PRIME NUMBER\n"); 
scanf("%d",&p); 
flag=prime(p); 
if(flag==0) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER ANOTHER PRIME NUMBER\n"); 
scanf("%d",&q); 
flag=prime(q); 
if(flag==0||p==q) 
{ 
    printf("\nWRONG INPUT\n"); 
    getch(); 
    exit(1); 
} 
printf("\nENTER MESSAGE\n"); 
fflush(stdin); 
scanf("%s",msg); 
for(i=0;msg[i]!=NULL;i++) 
m[i]=msg[i]; 
n=p*q; 
t=(p-1)*(q-1); 
ce(); 
printf("\nPOSSIBLE VALUES OF e AND d ARE\n"); 
for(i=0;i<j-1;i++) 
printf("\n%ld\t%ld",e[i],d[i]); 
encrypt(); 
decrypt(); 
getch(); 
} 
int prime(long int pr) 
{ 
int i; 
j=sqrt(pr); 
for(i=2;i<=j;i++) 
{ 
    if(pr%i==0) 
    return 0; 
} 
return 1; 
} 
void ce() 
{ 
int k; 
k=0; 
for(i=2;i<t;i++) 
{ 
    if(t%i==0) 
    continue; 
    flag=prime(i); 
    if(flag==1&&i!=p&&i!=q) 
    { 
        e[k]=i; 
        flag=cd(e[k]); 
        if(flag>0) 
        { 
            d[k]=flag; 
            k++; 
        } 
        if(k==99) 
        break; 
    } 
} 
} 
long int cd(long int x) 
{ 
long int k=1; 
while(1) 
{ 
    k=k+t; 
    if(k%x==0) 
    return(k/x); 
} 
} 
void encrypt() 
{ 
long int pt,ct,key=e[0],k,len; 
i=0; 
len=strlen(msg); 
while(i!=len) 
{ 
    pt=m[i]; 
    pt=pt-96; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
        k=k*pt; 
        k=k%n; 
    } 
    temp[i]=k; 
    ct=k+96; 
    en[i]=ct; 
    i++; 
} 
en[i]=-1; 
printf("\nTHE ENCRYPTED MESSAGE IS\n"); 
for(i=0;en[i]!=-1;i++) 
printf("%c",en[i]); 
} 
void decrypt() 
{ 
long int pt,ct,key=d[0],k; 
i=0; 
while(en[i]!=-1) 
{ 
    ct=temp[i]; 
    k=1; 
    for(j=0;j<key;j++) 
    { 
        k=k*ct; 
        k=k%n; 
    } 
    pt=k+96; 
    m[i]=pt; 
    i++; 
} 
m[i]=-1; 
printf("\nTHE DECRYPTED MESSAGE IS\n"); 
for(i=0;m[i]!=-1;i++) 
printf("%c",m[i]); 
}

Answer 3

I don't have the answer, but if the same code compiled with two different compilers gives different answers I would guess that some of the types are of different size or you are implicitly relying on undefined behaviour somewhere.

The first thing you should do is, given the same prime number pairs, check that all the constants you generate come out the same in both implementations. If not, your key pair generation algorithms are at fault.

The next thing is to make sure that your input data for encryption is absolutely identical on both systems. Pay particular attention to how you deal with end of line characters. Bear in mind that, on Windows, end of line is \r\n and on Linux it is \n. Most Windows library implementations will convert \r\n to \n as the file is read in if "r" is supplied as the mode parameter to fopen(). Your implementation might be different.

Finally, whatever the problem is, on no account ever use gets() If you even catch yourself thinking about using it again, you should remove the frontal lobes of your brain with an ice pick.

Answer 4

Following the practical notes at the end of the linked page you would arrive at something like this for the prime generation:

unsigned int get_prime(int e)
{
    while (true)
    {
        unsigned int suspect = 1 + (unsigned int)(65535.0 * rand() / (RAND_MAX + 1.0));
        suspect &= 0x0000FFFF; // make sure only the lower 16bit are set
        suspect |= 0xC001; // set the two highest and the lowest bit
        while (!test_prime(suspect))
        {
            suspect += 2;
        }
        if (suspect < 65536 && gcd(e, suspect - 1) == 1)
            return suspect;
    }
}

test_prime is supposed to be an implementation of the Miller-Rabin test. The function above makes certain assumptions and has some drawbacks:

• int is 32 bit
• RAND_MAX is larger than 65536
• rand() is usually not a good random number generator to use for serious encryption
• The generated primes are 16bit so obviously not large enough for serious encryption anyway

Don't use this in any production code.

According to the article it seems ok to choose e fixed.

Answer 5

This formula works for this specific case, but not all cases.

import math

p = 19
q = 17
e = 7

n = p * q #public key

m = 88 #message

c = (m**e) % n #encoded message

phi_of_N = (p-1) * (q-1)

ed = (phi_of_N * (e-1)) + 1

d = math.ceil(ed / e)

ed_valid_check = ed % phi_of_N

decoded = (c**d) % n

print(f'public key = n == {n}')
print(f'message = m == {m}')
print(f'encoded message = c == {c}')
print(f'phi_of_N == {phi_of_N}')
print(f'ed == {ed}')
print(f'd == {d}')
print(f'ed_valid_check. Should equal 1 == {ed_valid_check}')
print(f'Decoded Message: {decoded}')

It also works for these values.

p = 23
q = 29
e = 3