The purpose of this paper is to write a cryptosystem encoding RSA code in C language and verify it mathematically. RSA is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public, and it is different from the decryption key which is kept secret.
Procedure:
Choose two prime numbers p and q (these are your inputs). Suppose that you need to send a message to your friend, and you implement the RSA algorithm for secure key generation. You need public and private keys (these are your outputs). You are free to choose other parameters or inputs if you need any. Write a program for the RSA algorithm using any programing language such as C to generate your public and private key.
Your program will display the following:
(1) public and private keys
(2) your given message and encrypted message
(3) a message for any wrong inputs such as “you entered a number, which is not a prime.”
Table of Contents
1. Objectives
2. Components
3. Design - Procedure
4. RSA - Mathematical
5. Conclusions
1. Objectives
The purpose of this paper is to write a cryptosystem encoding RSA code in C language and verify it mathematically.
RSA is one of the first public-key cryptosystems and is widely used for secure data transmission. In such a cryptosystem, the encryption key is public, and it is different from the decryption key which is kept secret.
2. Components
Laptop with Linux running
3. Design - Procedure
Choose two prime numbers p and q (these are your inputs). Suppose that you need to send a message to your friend, and you implement the RSA algorithm for secure key generation. You need public and private keys (these are your outputs). You are free to choose other parameters or inputs if you need any. Write a program for the RSA algorithm using any programing language such as C to generate your public and private key.
Your program will display the following:
(1) public and private keys
(2) your given message and encrypted message
(3) a message for any wrong inputs such as “you entered a number, which is not a prime.”
To do that we used the following code:
Abbildung in dieser Leseprobe nicht enthalten
To verify the proper working of the code and the results we used mathematical calculations.
4. RSA - Mathematical
Steps of RSA implementation:
1. Select two prime numbers, p = 3 and q = 11
2. Calculate n = pq = 3 x 11 = 33
3. Calculate m = (3- 1) (11 - 1) = 2 x 10 = 20
4. Select e such that e is relatively prime to m = 20 and less than m, 1 < e < 20
gcd (e, 20) = 1
20 = 1 x 2 x 10
= 1 x 2 x 2 x 5
= 1 x 22 x 5
Assume that we take the smallest prime number in between of 2, 5 to 20, so e = 3
You also can take other value as long as it fulfils the conditions – it must be relatively prime with 20 and it is less than 20
. Determine d such that de = 1 mod 20 and d < 20
de mod m = 1
d x 3 = (? X 20) + 1
Abbildung in dieser Leseprobe nicht enthalten
Find the value which when the results mod 3 with no remainder
The correct value is d = 7, because
7 x 3 = 21 = 1 x 20 + 1
You also can take other value as long as it is a positive integer
Therefore, n = 33, m = 20, e = 3, d = 7
The resulting keys are:
Public key = {e, n} and Private key = {d, n}
Public key = {3, 33} and Private key = {7, 33}
Assume that P is the plaintext and C is the ciphertext
The encryption is C = P3 mod 33
The decryption is P = C7 mod 33
Public key = {e, n} and Private key = {d, n}
Public key = {3, 33} and Private key = {7, 33}
Given P = 6
The encryption is C = P3 mod 33
C = 63 mod 33
= 216 mod 33
= 18
The decryption is P = C7 mod 33
P = 187 mod 33
= 6
We then input the same numbers as the example and check the result produced by the code.
We first inserted number 8 which is not a prime number and the program responded correctly that it is not a prime number.
The prime input numbers inserted, according to the example, were 3 and 11 and then e was chosen as e=3. Then P=6 to be encrypted was chosen. The results and calculations were as follows in the next picture with public key {3,13} and Private key (7,13} The code produced a correct encrypted message for P as 18 and correct decrypted message as 6, verifying example 3.
Abbildung in dieser Leseprobe nicht enthalten
The code in text, according to the instructions, is as follows:
-- #include <stdio.h>
-- #include <stdlib.h>
-- #include <string.h>
-- #include <math.h>
-- #include <ctype.h>
long int p,q,t=0,n,m,d,pp,pp2,P,C,flag=0;
int a,b,i,j;
int count;
double em,en,en2;
double ez,ez2=5.0;
int i2=1;
int gcd(int a)
{
// Finds the GCD and then asks the user to pick one of the related prime numbers between 1<e<m
int remainder = 2;
int divident,divisor;
// printf("Enter Number\n");
// scanf("%d",&p);
for(i = 2 ; i < a ; i++){
divident = a;
divisor = i;
while(divisor != 0){
remainder = divident % divisor;
divident = divisor;
divisor = remainder;
}
if(divident == 1){
printf("Relatively Prime Number is : %d \n" ,i);
}
}
printf("\nChoose a number\n");
scanf("%d", &pp);
return pp;
}
double de(int m, int pp2)
{
//Function de will do the operation ((i2*m)+1)/e
//i2 is the counter number
//If the operation has any remainders, it will loop back
em = (i2*m)+1;
// printf("\nw %f\n",em);
en2 = em;
en = em/pp2;
// printf("\nwo %f\n",en);
ez = fmod(em,pp2);
// printf("\nwo2 %f\n",ez);
if(ez!=0){
i2++;
return de(m,pp2);
}
return en;
}
int EncryKey(int count, int n){
int startP,x=0,Cnew;
printf("\nChoose a value for P: ");
scanf("%d",&startP);
// printf("%d", startP);
x = pow(startP, count);
Cnew = x%n;
// printf("\n%d\n",Cnew);
return Cnew;
}
int DecryKey(int C, int d, int n){
int Pnew, x=0;
x = pow(C, d);
// printf("\n%d\n",x);
Pnew = x%n;
// printf("\n%d\n",Pnew);
return Pnew;
}
I nt main()
{
// clrscr();
printf("\nEnter the first prime number: ");
scanf("%d",&p);
t=p/2;
for(i=2;i<=t;i++){
if(p%i==0){
printf("\nYou entered a number which is not a prime\n"); //If it's not a prime it will loop back to main and ask again
// getch():
return main();
}
}
m=0;
printf("\nEnter the second prime number: ");
scanf("%d",&q);
t=q/2;
for(i=2;i<=t;i++){
if(q%i==0){
printf("\nYou enterered a number which is not prime\n"); //If it's not a prime it will loop back to main and ask again
return main();
}
}
n = p*q;
m = (p-1)*(q-1);
// printf("%d\n",m);
count = gcd(m);
d = de(m,count);
C = EncryKey(count, n);
P = DecryKey(C, d, n);
printf("\nThe public key is {%d, %d}\n", count, n); //The following will print the private, public keys and the encrypted message
printf("\nThe private key is {%d, %d}\n", d, n);
printf("\nThe encypted message is: %d\n",C);
printf("\nThe decrypted message is: %d\n",P);
return 0;
}
5. Conclusions
The RSA code was created correctly using C language and proven accordingly with the numerical example .
Frequently Asked Questions About the RSA Cryptosystem in C Language
What is the objective of this paper?
The purpose of this paper is to write a cryptosystem encoding RSA code in the C language and to verify it mathematically. RSA is used for secure data transmission where the encryption key is public and different from the secret decryption key.
What are the components required to implement the RSA cryptosystem described in this paper?
The primary component needed is a laptop with Linux running.
What is the general procedure for designing and implementing the RSA algorithm as described in this paper?
The procedure involves choosing two prime numbers (p and q), implementing the RSA algorithm to generate public and private keys, and writing a program (e.g., in C) to perform this key generation. The program should display the public and private keys, the original message and the encrypted message, and provide error messages for invalid inputs (e.g., non-prime numbers).
How does the RSA algorithm work mathematically, as explained in this paper?
The RSA implementation involves selecting two prime numbers (p and q), calculating n = pq, and m = (p-1)(q-1). A value 'e' is chosen such that it's relatively prime to 'm' and less than 'm'. Then, 'd' is determined such that de = 1 mod m. The public key is {e, n} and the private key is {d, n}. Encryption is performed as C = Pe mod n, and decryption as P = Cd mod n, where P is the plaintext and C is the ciphertext.
What is an example of RSA implementation, including values used for p, q, e, d, and the encryption/decryption process?
An example implementation uses p = 3, q = 11, n = 33, m = 20, e = 3, and d = 7. The public key is {3, 33} and the private key is {7, 33}. For plaintext P = 6, the encryption process yields C = 63 mod 33 = 18. The decryption process yields P = 187 mod 33 = 6.
What are the expected program outputs when implementing the RSA algorithm in C?
The program should display the public and private keys, the original message, the encrypted message, and an error message if a user inputs a non-prime number.
What C code is provided in the document?
The document includes a C implementation of the RSA algorithm, including functions for GCD calculation, determining 'd' (the private key component), encryption, and decryption. It features prime number input validation, public/private key generation, encryption of a plaintext value, and decryption of the resulting ciphertext.
What is the conclusion of this paper?
The RSA code was created correctly using the C language and verified with a numerical example.
- Quote paper
- Alexios Iosif Kotsis (Author), 2019, Writing a Cryptosystem Encoding RSA Code in C Language, Munich, GRIN Verlag, https://www.grin.com/document/512169
