Skip to main content
[ "article:topic", "showtoc:no", "license:ccbync", "authorname:mrosulek" ]
Engineering LibreTexts

2: The RSA Function

  • Page ID
    7398
  • The RSA function is defined as follows:

    • Let p and q be distinct primes (later we will say more about how they are chosen), and let N = pqN is called the RSA modulus.
    • Let e and d be integers such that ed ≡ϕ(N1. That is, e and d are multiplicative inverses mod ϕ(N) — not mod Ne is called the encryption exponent, and d is called the decryption exponent. These names are historical, but not entirely precise since RSA by itself does not achieve CPA security.
    • The RSA function is: m ↦ me % N, where m ∈ ℤN
    • The inverse RSA function is: c ↦ cd % N, where c ∈ ℤN .

    Essentially, the RSA function (and its inverse) is a simple modular exponentiation. The most confusing thing to remember about RSA is that e and d “live” in ℤϕ(N), while m and c “live” in ℤN.

         Let’s make sure the the function we called the “inverse RSA function” is actually in inverse of the RSA function. The RSA function raises its input to the e power, and the inverse RSA function raises its input to the dpower. So it suffices to show that raising to the ed power has no effect modulo N.

         Since ed ≡ϕ(N) 1, we can write ed = (N) + 1 for some integer t. Then:

    Figure13-5.jpg

     

    Note that we have used the fact that mϕ(N) ≡N 1 from Euler’s theorem.

     

    Security Properties

    In these notes we will not formally define a desired security property for RSA. Roughly speaking, the idea is that even when N and e can be made public, it should be hard to compute the operation c ↦ cd % N. In other words, the RSA function m ↦ me % N is:

    • easy to compute given N and e
    • hard to invert given N and e but not d
    • easy to invert given d