Question

Describe in about 200-300 words the RSA encryption algorithm,
Including:
*the method of encryption and decryption
*the three key theorems on which the algorithm depends
*the reason for the security of the algorithm

Thank you!

Answer 1

RSA i beleieve deals with 2 large primes and the totient function

Answer 2

im not about to type up 200 to 300 words on it tho, youll have to do that yourself

Answer 3

spose you are given a plaintext message: P

we can encrypt it with a key "e" such that \(gcd(e,\phi(n))\) = 1

and n is the product of 2 large primes

Answer 4

this ensures us that a decryption key can be produced to uncode it all

Answer 5

i had a powerpoit on it for the presentation i did in my number theory class; but the schools website is down at the moment

Answer 6

I understand,

I have done this so fay from my notes but i dont understand what is what.


SO

1) Choose two distinct primes, p and q
2) Find n such that n=pq
3) Use Q(n)= (p-1)(q-1) Q = phi, (*****)
4)Choose e such that 1<e<Q(n)
e is publicly seen, and is relativly prime to Q(n)
5) Find d, which is multiplicatively inverse of e in Z _Q(n)

i.e. de=1(mod(Q(n)) (****)

d can be found using Euclidean algorithm and is a private key

then i get lost,

how do you decrypt the message? by using M, original message

M=c^5 (mod(n))? where c is the coded message? (****)



(****) which theorems are used here?

Answer 7

one key aspect of the totient function is that it is a multiplicative function so long as the factors of a number are relatively prime.; there is a more complicated method for finding the phi value of any number. The phi value is simply the number of relatively prime values that are less the number; for example:

the number 8: 1 2 3 4 5 6 7 8
^ ^ ^ ^
there are 4 numbers less than 8 that are relatively prime
to 8; (a,8)=1

the phi value of 8 is 4

the number 9: 1 2 3 4 5 6 7 8 9
^ ^ ^ ^ ^ ^
i count 6 of them

the phi value of 9 is 6

the phi value of a prime number is simply all the numbers less than it; phi(7) = 6, phi(13)=12, phi(17)=16 why? because a prime number is prime ....


now to explain what it means to be a multiplicative function:

f(ab) = f(a) * f(b) simple enough; and this is true for phi given that a and b are relatively prime.

since 8 and 9 are relatively prime then,

phi(72) = phi(8*9) = phi(8) phi(9) = 4 * 6 = 24

the reason for picking 2 large primes for the "n" is so that you can construct this phi value in a simple manner i believe

Answer 8

another thrm is that \[a^{\phi(n)}\cong a~(mod~n)\]
proof:

let "n" be a number with the set of relatively primes: {r1,r2,r3,...,r phi(n)}, since there are phi(n) relatively primes by definition.

the product of these numbers is then: r1 r2 r3 ... r phi(n) = k

therefore \(k\cong 1~(mod~n)\)

lets take a number a such that (a,n) = 1; and multiply each r value in the set
\[a r_1~ a r_2 ~ a r_3 ... ar_{ phi(n)} = a^{\phi(n)}k\]
since (k,n)=1; and (a,n)=1; therefore a^(phi(n)) = 1 (mod n)

Answer 9

how does this help us find an inverse?

Answer 10

\[a*a^{\phi(n)-1}=a^{\phi(n)}\]

Answer 11

Eulers thrm is the backbone of the RSA

Answer 12

aϕ(n)≅a (mod n), shouldnt this be

aϕ(n)≅ 1 (mod n) ?