# bquran.co

# Writing Rsa Key

$ ls -alh -rw-r-r- 1 mattias 1.7K certificate.crt -rw-r-r- 1 mattias 1.6K certificate.key. You can use the certificate.key as the key for your SSL configurations. It doesn't have a password associated with it, that's what the -nodes (No DES encryption) option was for when running the openssl command. Generating RSA keys Create two large prime numbers namely p and q. The product of these numbers will be called n, where n= p.q Generate a random number which is relatively prime with (p-1) and (q-1). Let the number be called as e. Calculate the modular inverse of e. The calculated inverse will be.

When using RSA you must ensure that you are using large enough keys, proper data padding schemes, constant time operations, etc.

The following are 30 code examples for showing how to use Crypto.PublicKey.RSA.generate.These examples are extracted from open source projects. You can vote up the ones you like or vote down the ones you don't like, and go to the original project or source file by following the links above each example. Sr App Engineer. Hey guys, I wanted to write a little bit about RSA cryptosystem. RSA is an asymmetric system, which means that a key pair will be generated (we will see how soon), a public key and a private key, obviously you keep your private key secure and pass around the public one. The algorithm was published in the 70’s by Ron R ivest, Adi S hamir, and Leonard A dleman, hence RSA, and it sort of implement’s a trapdoor function such as Diffie’s one.

Let's explore what happens when you don’t get some of this right in three different ways (these various issues have been known for a long time, however I figured it would be interesting to re-visit them).

### 2 minute refresher on RSA

RSA is a public key cryptosystem developed by Rivest, Shamir and Adleman in 1977. It is still the main primitive used by TLS (https), GPG, ssh, etc.

Public key crypto involves two keys: a public key and a private key. A user (Bob) publishes their public key and keeps the private key secure. Anyone can securely send messages to Bob by encrypting the contents using the public key. Only Bob who knows the private key can decrypt the messages.

RSA is based on the fact that it's easy to create and multiply two large prime numbers but it's hard to factorize the product. RSA also relies on modular exponentiation (`a^e mod n`

) being a one-way function (given `c ≡ a^e mod n`

, computing `c`

is easy but finding `a`

given `c`

, `e`

and `n`

is hard).

The key generation algorithm boils down to:

- choose two distinct prime numbers
`p`

and`q`

. (Look up how this is actually done, it's interesting and has caused security flaws in the past). - compute
`n = p*q`

. The length of`n`

(in bits) is going to be the key length. - compute
`φ = (p − 1)*(q − 1)`

. - choose
`e`

, typically 3 or 65537. - compute
`d ≡ e^-1 mod φ`

(also look up how this is done).

- public key is the pair
`(n, e)`

- private key is the pair
`(n, d)`

Encryption is then performed using modular exponentiation. In this post, we ignore the fact that RSA encryption should always be combined with a secure encryption scheme (e.g. OAEP). Normally, you don't process plaintext with RSA but instead generate a fixed size random session key.

The RSA part of the encryption process boils down to:

- convert the message into a big integer.
- compute
`c ≡ m^e mod n`

And decryption ends up being the same operation with a different exponent:

`c^d ≡ (m^e)^d ≡ m (mod n)`

See Wikipedia's page on RSA for more info.

### Cracking a weak RSA key

Let’s create a weak key and crack it. We’ll use openssl to create the key and encrypt a message. We’ll then use Ruby to factorize the public key and re-create the private key. Ruby makes handling bignums implicit (which is nice), but keep in mind that its handling of bignum is very slow (100 times slower than javascript and at least 3 orders of magnitude slower than native code).

#### Key generation

The first step is to create a weak key. We decided to go with a 64 bit RSA key because 64 bits ends up taking me a few minutes to break on my laptop. Feel free to try breaking larger keys, such as 128, 256 or 512 bit keys.

Notice how openssl doesn’t throw any warnings!

The key follows the following format:

`exponent1`

, `exponent2`

and `coefficient`

arestored in the private key for optimizing purpose.

We want to throw away the private part of the key, so we extract the public key with `-pubout`

:

Finally, let’s encrypt a message using the public key.

#### Factorization

To factorize small.pem, we simply iterate through all the numbers from 2 to the square root of `n`

(we can stop at the square root r of n because if a number n is divisible by m with m>r, then n is also divisible by n/m and n/m<r).

As a micro optimization (makes the code run ~4x faster), we start by checking if `n`

is divisible by 2, 3, 5 and we then go in chunks of 30 (30 comes from 2*3*5).

#### Re-creating the private key

Once we have factorized `n`

, we can recreate the private key which allows us to decrypt cipher.txt.

*Thankfully, keys are typically 2048 bits or longer, making this attack infeasible.*

### Cracking a weak RSA message

Encrypting a message involves computing `m^e mod n`

. If `e`

is a small value (e.g. 3) and `m^e`

is less than `n`

, the modulo does not do anything.

The original message is revealed by computing the `e`

th root.

#### Message generation

#### Computing the nth root

We compute the nth root using Newton’s method. The code was easily found by Googling around.

Notice how openssl doesn’t print any warnings.

In the case where we don't know the exponent's value, we can try a few different options.

*When using RSA with random session keys, this case is unlikely to occur.*

### Same RSA message encrypted multiple times

If a message is encrypted `e`

times, we can use the Chinese Remainder Theorem (see this post) to decrypt the ciphertext.

The theorem says that given:

`m^e mod A`

`m^e mod B`

`m^e mod C`

- ...

It is possible to compute `m^e (mod A*B*C*...)`

.

This means we can convert three identical messages encrypted to three recipients into the weak message case above. This is possible because the message is going to be smaller than the product A*B*C.

*This is why RSA needs a randomized padding scheme.*

## 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 2 ^{2} 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 = P ^{3} mod 33**

The decryption is **P = C ^{7} 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 = P ^{3} mod 33**

**C = 6 ^{3} mod 33**

**= 216 mod 33**

** = 18**

The decryption is **P = C ^{7} mod 33**

**P = 18 ^{7} 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 Numbern');**

**// 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 numbern');**

** 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 %fn',em);**

** en2 = em;**

** en = em/pp2;**

**// printf('nwo %fn',en);**

** ez = fmod(em,pp2);**

**// printf('nwo2 %fn',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: ');**

### Writing Rsa Key Format

** scanf('%d',&startP);**

**// printf('%d', startP);**

** x = pow(startP, count);**

** Cnew = x%n;**

**// printf('n%dn',Cnew);**

** return Cnew;**

**}**

** int DecryKey(int C, int d, int n){**

** int Pnew, x=0;**

** x = pow(C, d);**

**// printf('n%dn',x);**

### Writing Rsa Key Format

** Pnew = x%n;**

**// printf('n%dn',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%i0){**

### Writing Rsa Keywords

** printf('nYou entered a number which is not a primen'); //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%i0){**

** printf('nYou enterered a number which is not primen'); //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('%dn',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: %dn',C);**

** printf('nThe decrypted message is: %dn',P);**

** return 0;**

**}**

## 5. Conclusions

The RSA code was created correctly using C language and proven accordingly with the numerical example **.**

**[...]**