Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

Rezz5

  • 3 years ago

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!

  • This Question is Closed
  1. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  2. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  3. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  4. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  5. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  6. Rezz5
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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?

  7. jishan
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    1 Attachment
  8. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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

  9. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    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)

  10. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    how does this help us find an inverse?

  11. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  12. amistre64
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

    Eulers thrm is the backbone of the RSA

  13. Rezz5
    • 3 years ago
    Best Response
    You've already chosen the best response.
    Medals 0

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

  14. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy