Here's the question you clicked on:
Rezz5
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!
RSA i beleieve deals with 2 large primes and the totient function
im not about to type up 200 to 300 words on it tho, youll have to do that yourself
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
this ensures us that a decryption key can be produced to uncode it all
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
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?
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
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)
how does this help us find an inverse?
\[a*a^{\phi(n)-1}=a^{\phi(n)}\]
Eulers thrm is the backbone of the RSA
aϕ(n)≅a (mod n), shouldnt this be aϕ(n)≅ 1 (mod n) ?