Given two prime numbers p & q, where p=3 and q=11.
Calculate n=p*q, so 3*11=33
N is for the modulus for the public and private keys, so N=3*11=33
Calculate the totient phi(n)=(p-1) *(q-1)
phi(n)= (3-1) *(11-1) =2*10=20
Choose integer e (public key) which is given at e=3
Secret key is given by d which is:
e*d=1(mod phi(n))
3*d=1(mod 20)
Needing to find a value of d when divided by 20 has a remainder of 1, which 7.
The Encrypted Message # would be: (Message Equivalent #s^e (mod n)
Decrypted message Number would be: (Encrypted Message Number) ^d (mod n)
The Encrypted Message is: 19 01 14 17 32 03 28 32 18 05
p and q = 3 *11 = 33 = N
(p-1) * (q-1) = 20
e = 3
to find d I choose 21 d d 3*7 = 21 - 20 = 1
Message: 17 01 22 26 32 18 21 5
My ciphertext message is: 03 32 18 09 21 05 31 32 27 24 16 04 14 09 13 24 01 04 17 16 32 14 09
32 08 26 32 03 05 14 26 24 26 28 14 03 05 13 32 01 05 31 32 14 17 26 32 19 09 28 14 32 24 26
12 01 14 01 08 12 26 32 14 09 32 19 16 32 19 01 10 09 24.
I found d by first calculating N and φ. Since e=3, I next had to ensure gcd (3, φ) = 1. Finally, to find
d I found the inverse of e mod φ. I tried to explain my work to the best of my ability without
revealing the answers.
3 32 26 5 28 9 16 26 31 32 14 17 20 32 28 16 1 5 5 3 5 13 32 14 24 26 26 28
(3-1) *(11-1) = 2*10 = 20
3*d=1*mod20
d = 7
Given the prime number p = 3, q = 11, able to calculate N = p *q | 3 * 11 = 33, φ = (p - 1) *(q - 1)
= 20. which sets up the modulo e*d mod 20 = 1. provided e = 3 able to calculate d = 7. With all
those components we can implement the RSA cryptosystem to send and receive messages. I am
grateful for this class as it was intensive and a great beating into shape after a hiatus of math
courses. I learned a lot and towards the end enjoyed it. Thank you!
Encrypted with no punctuation:
13 24 01 04 17 32 14 17 26 09 24 16 32 12 26 31 32 14 09 32 08 03 05 18 09 24 19 01 14 03 27 28
RSA is an asymmetric crypto-system, developed in 1978 by Rivest, Shamir and Adlema. The
fundamental idea was to develop a trap-door function on a set X, meaning that it was to be quite
easy for an individual to generate a set of integers through a function E, but extremely difficult for
another person to do so.
RSA uses a pair of keys to encrypt a plain-text message, into cypher-text. These keys are the public
key, which is known to everyone, and the private key, which is kept secret by the generator of
these keys (Coffey,2017). To communicate, the recipient needs to have a public key, and a private
key. To obtain these, one runs a key generation algorithm, which generates two large prime
numbers, P and Q. These two numbers are mathematically related. However, it is computationally
infeasible to calculate the other number, given only one of these. Herein is one of the strengths of
RSA.
The receiver retains one of these numbers, P, as the private key, and then shares the other
number, Q, as the public key, with the other sender. To pass a message 'm', the sender first
encrypts this plain-text with an encryption algorithm, using public key Q, of the recipient. Only the
person with the private key P can decrypt this message, as there is no other key that can do so.
The resultant text after the encryption process is called the cypher text, C, and is derived as
follows,
C = me mod n
Once the cypher-text is generated, it can then be transmitted through an insecure channel,
without fear of eavesdropping or modification by an intruder. When the message reaches the
targeted recipient, he/she can use the Private key, Q, to decrypt the message, using a decryption
algorithm.
P = Cd mod n
For this crypto-system to be effective, it is important to use large numbers as the keys, to make
cryptanalysis much more difficult. It is also important to use digital signature schemes. These will
verify if messages reaching the recipient from a sender S are really from S, and have not been
forged by a different sender, or modified during transmission.
If p = 3 and q = 11, then N = p*q = 3*11 = 33. Next (p-1) * (q-1) = 20. If e = 3 and 3dmod20=1
then d = 7 and to encrypt we will use the formula
c=memodN
. Here is my message: 32 is for a space
14 17 03 28 32 27 09 21 24 28 26 32 21 28 26 28 32 12 09 13 03 27 32 23 17 03 27 17 32 01 04
04 12 03 26 28 32 14 09 32 28 09 18 14 23 01 24 26
With given the two-prime number of p and q we would say p = 3 and q = 11. We would calculate
that n = pq because n would be the modulars for public and private keys. With that being said we
can say that n = 3*11 = 33. Breaking down this process further we would then calculate the
totient phi (p - 1) (q - 1) and phi (n) = (3-1) *(11 -1) = 2*10 = 20. Now with choosing an integer we
say e because it is a public key so e = 3. With a secret key given by initial d which would be from
the following formula of: e*d = 1 (mod 20). This would consequently imply that the value of d is
divided by 20 yields 1 as a reminder. Therefore, we are left with d = 7. Now to find the encrypted
message number we would say ^e (mod n) and that the decrypted message number = that of
encrypted message number ^d (mod n).
The phrase does not have any punctuation or special characters.
Cyphertext: 03 32 18 09 21 05 31 32 14 24 26 26 32 14 24 01 22 26 24 28 01 12 28 32 03 05 14 26
24 26 28 14 03 05 13
I calculated d by using the Extended Euclidean Algorithm.
de = 1 mod 20
? x 3 = 1 mod 20
27 x 3 = 1 mod 20
The public key would be (33, 30) and the private key (33, 27).
I found d by using Euclid's Algorithm to find some A and B such that:
A x e + B x φ = 1.
d = A, which is the inverse of e mod φ.
I am using 27-30 for the characters., - ' respectively.
EDITED SHORTER PHRASE:
03 32 26 05 10 09 16 26 31 32 01 12 13 09 24 03 14 17 19 28 07 32 26 21 12 26 24 32 13 24 01
04 17 28 07 32 08 18 28 07 32 01 05 31 32 31 18 28 15
END EDIT
17 26 12 12 09 32 26 22 26 24 16 09 05 26 07
14 17 26 32 14 17 03 05 13 28 32 03 32 18 09 21 05 31 32 19 09 28 14 32 03 05 14 26 24 26 28
14 03 05 13 32 01 05 31 32 24 26 12 26 22 01 05 14 32 03 05 32 14 17 03 28 32 27 09 21 24 28
26 32 23 26 24 26 32 14 17 26 32 22 01 24 03 09 21 28 32 01 12 13 09 24 03 14 17 19 28 15 32
14 17 26 28 26 32 03 05 27 12 21 31 26 32 08 24 26 01 31 14 17 02 18 03 24 28 14 32 01 05 31
32 31 26 04 14 17 02 18 03 24 28 14 32 28 26 01 24 27 17 26 28 07 32 01 28 32 23 26 12 12 32
01 28 32 04 24 03 19 06 28 32 01 12 13 09 24 03 14 17 19 15 32 14 17 26 28 26 32 23 03 12 12
32 01 12 12 32 04 24 09 22 26 32 21 28 26 18 21 12 32 03 05 32 19 16 32 10 09 21 24 05 26 16
32 14 09 23 01 24 31 32 19 16 32 27 09 19 04 21 14 26 24 32 28 27 03 26 05 27 26 32 31 26 13
24 26 26 15 32 03 32 01 12 28 09 32 26 05 10 09 16 26 31 32 23 09 24 11 03 05 13 32 23 03 14
17 32 17 01 28 28 26 32 31 03 01 13 24 01 19 28 32 01 05 31 32 18 03 05 31 03 05 13 32 26 21
12 26 24 32 27 03 24 27 21 03 14 28 32 01 05 31 32 14 24 01 03 12 28 32 03 05 32 13 24 01 04
17 28 15
03 32 23 03 28 17 32 16 09 21 32 01 12 12 32 14 17 26 32 08 26 28 14 32 03 05 32 14 17 26 32
18 21 14 21 24 26 07
27 17 24 03 28 14 09 04 17 26 24
Reference
Coffey, N. (2017). RSA key lengths. Javamex.com. Retrieved February 24,2022, from
https://www.javamex.com/tutorials/cryptography/rsa_key_length.shtml
