The RSA Encryption Scheme General Example

Each RSA number is a semiprime (A nu mber is semiprime if it is the product of tw o primes ) There are two labeling schemes by the number of decimal digits: RSA-100, RSA Numbers x x , RSA-500, RSA-617 by the number of bits: RSA-576, 640, 704, 768, 896, , 151024 36, 2048

1) A very simple example of RSA encryption

1) A very simple example of RSA encryption This is an extremely simple example using numbers you can work out on a pocket calculator (those of you over the age of 35 45 can probably even do it by hand) 1 Select primes p=11, q=3 2 n = pq = 11 3 = 33 phi = (p-1)(q-1) = 10 2 = 20 3 Choose e=3

The RSA Encryption Scheme General Example

The RSA Encryption Scheme Suppose Alice wants her friends to encrypt email messages before sending them to her Computers represent text as long numbers (01 for \A", 02 for \B" and so on), so an email message is just a very big number The RSA Encryption Scheme is often used to encrypt and then decrypt electronic communications General Alice

RSA { the Key Generation { Example

RSA { Encryption/Decryption { Example The encryption algorithm E: Everybody can encrypt messages m(0 m

Sur l’algorithme RSA

Sur l’algorithme RSA Le RSA a´et´e invent´e par Rivest, Shamir et Adleman en 1978 C’est l’exemple le plus courant de cryptographie asym´etrique, toujours consid´er´e comme surˆ , avec la technologie actuelle, pour des cl´es suﬃsament grosses (1024, 2048 voire 4096 bits)

Lecture 12: Public-Key Cryptography and the RSA Algorithm

12 2 The Rivest-Shamir-Adleman (RSA) Algorithm for 8 Public-Key Cryptography — The Basic Idea 12 2 1 The RSA Algorithm — Putting to Use the Basic Idea 12 12 2 2 How to Choose the Modulus for the RSA Algorithm 14 12 2 3 Proof of the RSA Algorithm 17 12 3 Computational Steps for Key Generation in RSA 21

Public Key CryptoSystems RSA Algorithm

THE RSA CRYPTOSYSTEM 2 1 RSA Algorithm 13 2 1 1 Key Generation 13 2 1 2 RSA Encryption 14 2 1 3 RSA Decryption 14 2 1 4 Example of RSA 14 2 2 The Security of RSA 15 2 2 1 Brute force 15 2 2 2 Mathematical attacks 16

Introduction à la cryptographie TD6 – RSA : exemples simples

de RSA Ensuite, nous allons voir à quel point la cryptographie est un parcours semé d’em-bûches, y compris lors de l’implémentation d’une simple primitive Nous utiliserons pour cela l’exemple de l’algorithme de signature asymétrique RSA, telle qu’il est par exemple utilisé dans les cartes bancaires 1 Prérequis et premiers

[PDF] algorithme rsa pdf

[PDF] algorithme rsa exercice corrigé

[PDF] cryptage rsa exemple

[PDF] cryptographie asymétrique algorithme

[PDF] chiffrement asymétrique et symétrique

[PDF] chiffrement asymétrique exemple

[PDF] cryptographie exercices corrigés pdf

[PDF] les nombres en lettres pdf

[PDF] les nombres en lettres de 0 ? 1000

[PDF] ap seconde chiffres significatifs

[PDF] chiffres significatifs excel

[PDF] les chiffres significatifs cours

[PDF] chiffres significatifs sinus

[PDF] precision d une mesure et chiffres significatifs

[PDF] chiffres significatifs exacts

The RSA Encryption Scheme

Suppose Alice wants her friends to encrypt email messages before sending them to her. Computers represent text as long numbers (01 for \A", 02 for \B" and so on), so an email message is just a very big number. The RSA Encryption Scheme is often used to encrypt and then decrypt electronic communications.

General

Alice's Setup:

Chooses two prime numbers.

Calculates the productn=pq.

Calculatesm= (p1)(q1):

Chooses numberseanddso thatedhas a

remainder of 1 when divided bym.

Publishes her public key (n;e).Example

Alice's Setup:

p= 11 andq= 3. n=pq= 113 = 33: m= (p1)(q1) = 102 = 20:

Ife= 3 andd= 7, thened= 21 has a

remainder of 1 when divided bym= 20.

Publish (n;e) = (33;3).

Bob encrypts a messageMfor Alice:

Finds Alice's public key (n;e).

Finds the remainderCwhenMeis divided

byn. Sends ciphertextCto Alice.Bob encrypts messageM= 14: (n;e) = (33;3).

When 143= 2744 is divided by 33, the re-

mainder isC= 5.

Sends ciphertextC= 5 to Alice.

Alice receives and decrypts ciphertextC:

Uses her private key (n;d).

Finds remainderRwhenCdis divided byn.

Rmatches the messageMthat Bob wanted

to send to Alice!Alice decrypts ciphertextC= 5: (n;d) = (33;7).

When 57= 78125 is divided by 33, the re-

mainder isR= 14.

R= 14 =M, the original message from Bob!

Questions

1. Callie wants to send the messageM= 13 to Alice. Using Alice's public and private keys,

calculate the ciphertextC, and the value forRwhen Alice recovers the message.

2. Dexter wants to set up his own public and private keys. He choosesp= 23 andq= 19 with

e= 283. Finddso thatedhas a remainder of 1 when divided by (p1)(q1).

Connection to the Real World

When your internet browser shows a URL beginning with https, the RSA Encryption Scheme is being used to protect your privacy. For

example, if you log in to Facebook, your computer plays the role of Alice and the Facebook server plays the role of Bob, encrypting and

decrypting the information passed back and forth. In practice, the primespandqare chosen to be very big numbers.

Mathematics is the foundation of modern encryption.

For more Real-World Problems Being Solved by Mathematics, visit http://www.cemc.uwaterloo.ca/resources/real-world.html.

Solution:

1.Callie encrypts messageM= 13:

Alice's public key is (n;e) = (33;3).

WhenMe= 133= 2197 is divided by 33, the remainder isC= 19.

Callie sends to Alice ciphertextC= 19.

Alice receives and decrypts ciphertextC= 19:

Alice uses her private key (n;d) = (33;7).

When 197= 893;871;739 is divided by 33, the remainder isR= 13.

R= 13 =M, the original message from Callie!

2. Withp= 23;q= 19, we havem= (p1)(q1) = 22(18) = 396.

We want to nddso thated= 283dhas a remainder of 1 when divided bym= 396. One way to do this is by simple trial and error, increasing the value ofduntil 283ddivided by 396 leaves a remainder of 1.Remainder when d283d283dis divided by 3961283283

2566170

384957

41132340

51415227

61698114

719811

We see thatd= 7 works; that ised= 2837 = 1981 leaves a remainder of 1 when divided by 396.
In general, trial and error could take a very long time, as the value ofdcould be a big number. Instead, an ancient technique called Euclid's Algorithm can be used to nddin the linear

Diophantine equation 283d+ 396y= 1.

For more Real-World Problems Being Solved by Mathematics, visit http://www.cemc.uwaterloo.ca/resources/real-world.html.

quotesdbs_dbs15.pdfusesText_21

[PDF] The RSA Encryption Scheme General Example

The RSA Encryption Scheme

General

Alice's Setup:

Chooses two prime numbers.

Calculates the productn=pq.

Calculatesm= (p1)(q1):

Chooses numberseanddso thatedhas a

Publishes her public key (n;e).Example

Alice's Setup:

Ife= 3 andd= 7, thened= 21 has a

Publish (n;e) = (33;3).

Bob encrypts a messageMfor Alice:

Finds Alice's public key (n;e).

Finds the remainderCwhenMeis divided

When 143= 2744 is divided by 33, the re-

Sends ciphertextC= 5 to Alice.

Alice receives and decrypts ciphertextC:

Uses her private key (n;d).

Finds remainderRwhenCdis divided byn.

Rmatches the messageMthat Bob wanted

When 57= 78125 is divided by 33, the re-

R= 14 =M, the original message from Bob!

Questions

1. Callie wants to send the messageM= 13 to Alice. Using Alice's public and private keys,

2. Dexter wants to set up his own public and private keys. He choosesp= 23 andq= 19 with

Connection to the Real World

Solution:

1.Callie encrypts messageM= 13:

Alice's public key is (n;e) = (33;3).

Callie sends to Alice ciphertextC= 19.

Alice receives and decrypts ciphertextC= 19:

Alice uses her private key (n;d) = (33;7).

R= 13 =M, the original message from Callie!

2. Withp= 23;q= 19, we havem= (p1)(q1) = 22(18) = 396.

2566170

384957

41132340

51415227

61698114

719811

Diophantine equation 283d+ 396y= 1.