If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Main content

RSA encryption: Step 2

Setting up a trapdoor one-way function. Created by Brit Cruise.

Want to join the conversation?

  • male robot hal style avatar for user Chris Seltzer
    Are these meant to be broken up like this? Also aren't the full videos already on the site?
    (35 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Alastair Carnegie
    mod(N) = (p - 1 )*(q - 1) where 'p' & 'q' are two equal length binary prime integers of uniform bit length, say 512 bits each resulting in a dual-prime composite of 1024 bit length.
    127, 63, 31, 15, 7, 3, 1,
    1 1 1 1 1 1 1
    1 0 0 0 0 0 0
    64 32 16 8 4 2 0
    So two primes of say 7 bit length would be primes between 67 & 127.
    67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127.
    Suppose we have a dual-prime composite 10057, we could divide by all the possible primes, and when we got to 89, BINGO! 89 x 113 = 10057.
    Interestingly, 101 x 101 = 10201, and 10201 - 10057 = 144 = 12 x 12. AND, 101 + 12 = 113, and 101 - 12 = 89.
    Also of note, there is an asymptopic series or sub ratios, 3:4, 4:5, , , .
    and 89 x 33 = 2937, & 113 x 26 = 2938. so the ratio is a perfect sub-ratio.
    This asymtotic series of sub-ratos is easy to calculate with basic algebra, and the result obtained within polynomial time constraints. So my question is, "Why do folk believe the factoring of any length dual-prime composite is exceptionally difficult? or of substantial asymetric complexity? "
    (6 votes)
    Default Khan Academy avatar avatar for user
    • blobby green style avatar for user de.li.chessguy
      Since nobody answered this and for anyone reading the comments:

      Your example used only 7 bits. That's nothing compared to 512 bits. 512 bits would be a number with about 150 digits (log10(2) is around 3.3 bits which mean every 3.3 bit in binary is one digit in decimal, 512/log10(2) is about 154).

      Now with 10 digits we already have about 400 million primes. You can begin to imagine how many primes there are with 150 digits. The number of primes smaller than n can be approximated with n/ln(n). n=150 would give us about 2*10^149. So the number of primes with 150 digits is in the magnitude of 10^149 (and 512 bit is actually 154 digits). That's just for finding prime numbers, after that you have to brute force the factorization.

      We do not have the computational power to even begin a brute force attack, although if quantum computers are invented it can be done (but we are not even close to that possibility yet).
      (11 votes)
  • piceratops ultimate style avatar for user christian
    at you mentioned Euclid . Who is Euclid?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • mr pink red style avatar for user Varun
      Euclid is a dead guy who discovered/invented Euclidean geometry, which is all the laws of geometry that govern our three-dimensional world. Basically, he's this dead guy who did a lot of cool things with numbers, kind of like another dead guy whose name is sort of similar named Euler.
      (10 votes)
  • blobby green style avatar for user andrew.comly
    I would like to thank the Khan Academy for the ambition to try to teach something as complex in nature as discrete logarithm, however I seem to have totally failed this lecture on the "RSA Encryption (step 2)" lecture(time period - ), more specifically I just can not understand how the formulas:
    (1) : m^e mod N == c
    (2) : c^d mod N == m
    logically lead to the equation:
    (final): (m^e)^d mod N == m

    First I will explain what I do understand. The first two equations teach that the message/data sent must be first encrypted (e), e.g. m^e mod N == c
    and then the message/data received must be decrypted (d), e.g. c^d mod N == m.

    Moreover this is to explain briefly how the message will be decrypted, and to point out that the original process used to encrypt the message/data must be reversed.
    However, using algebraic substitution, when one substitutes c = m^e mod N into the "c" of the decryption formula (c^d mod N == m), one is left with an algebraic knot:
    Orig: [c]^d mod N == m
    Sub: c == m^e mod N
    Knot: [m^e mod N]^d mod N == m

    The last line above is quite a problem because [m^e mod N]^d mod N
    does not equal to (m^e)^d mod N, anotherwords
    (m^e)^d NOT = [m^e mod N]^d.
    I showed this is not equal with the clinical values below: [ ** = ^ ]
    [code]
    $ ./modOfMod.sh
    Modular of a discrete log containing an identical modular
    Enter starting number> 243
    SingleModulo = R % 17; yy = ${SingleMod} ** e; yyy= $yy % 17
    Enter power > 5
    243: SingleModulo = 5 yy = 3125 yyy = 14
    244: SingleModulo = 6 yy = 7776 yyy = 7
    245: SingleModulo = 7 yy = 16807 yyy = 11
    246: SingleModulo = 8 yy = 32768 yyy = 9
    247: SingleModulo = 9 yy = 59049 yyy = 8
    248: SingleModulo = 10 yy = 100000 yyy = 6
    249: SingleModulo = 11 yy = 161051 yyy = 10
    250: SingleModulo = 12 yy = 248832 yyy = 3
    251: SingleModulo = 13 yy = 371293 yyy = 13
    252: SingleModulo = 14 yy = 537824 yyy = 12
    253: SingleModulo = 15 yy = 759375 yyy = 2
    254: SingleModulo = 16 yy = 1048576 yyy = 16
    255: SingleModulo = 0 yy = 0 yyy = 0
    256: SingleModulo = 1 yy = 1 yyy = 1
    257: SingleModulo = 2 yy = 32 yyy = 15
    258: SingleModulo = 3 yy = 243 yyy = 5
    259: SingleModulo = 4 yy = 1024 yyy = 4
    [/code]

    Through my above values test I have showed that the SingleModulo [m^e mod N] and yyy {[m^e mod N]^d mod N} are NOT equal.

    I just do not how Brit Cruise made the logical step to say that the two equations:
    m^e mod N == c
    c^d mod N == m
    lead somehow logically to the equation:
    (m^e)^d mod N == m

    The final equation I am clear on. Naturally I can see that there does certainly exist some number d that can reverse the effect e had on m before, that is the multiplication identity [ N * (1/N) =1]. The problem is simplly that I have absolutely no idea how he got from the two encrypt/decrypt problems to the final equation.

    I guess I am missing some fundamental understanding of mathematics. Can anyone help me?
    (5 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      (1) m^e mod N = c
      (2) c^d mod N = m
      substitute (1) into (2)
      (m^e mod N)^d mod N = m

      Believe it or not:
      (m^e mod N)^d mod N = (m^e)^d mod N
      This is not the same as saying:
      (m^e mod N)^d = (m^e)^d
      The final mod N on each side matters!
      Just because A mod N = B mod N, we can not conclude that A = B
      e.g.
      7 mod 4 = 11 mod 4
      3 = 3
      But it would be incorrect to say:
      7 = 11

      Proof that (m^e mod N)^d mod N = (m^e)^d mod N
      LHS (left hand side) = (m^e mod N)^d mod N
      RHS (right hand side) = (m^e)^d mod N
      We'll show that LHS = RHS

      By the quotient remainder theorem:
      A = B * Q + R where 0 < R < B and A,B,Q,R are integers
      So:
      m^e = N * Q + R

      LHS = (m^e mod N)^d mod N
      LHS = ((N * Q + R) mod N)^d mod N
      multiples of N are 0 under mod N, and R is < N so R mod N = R
      LHS = R^d mod N

      RHS = (m^e)^d mod N
      RHS = ( N * Q + R )^d mod N
      expand the terms
      RHS = ((N * Q)^d + (N * Q)^(d-1) * R^1 + ... + (N * Q)^1 * R^(d-1) + R^d) mod N
      apply mod N to all the terms in the brackets, multiples of N are 0 under mod N
      RHS = R^d mod N

      LHS = R^d mod N = RHS
      thus
      (m^e mod N)^d mod N = (m^e)^d mod N

      For more info on modular arithmetic check out these lessons:
      https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

      Hope this makes sense
      (4 votes)
  • blobby green style avatar for user Evan Gritter
    So in the equation M^(e) mod n all raised to the power of d = M () why wouldn't mod(n) also be raised to the power of D.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      There's a couple ways of thinking about this:

      Approach #1)

      m^e mod N ≡ c
      notice the ≡ is used, not the =

      m^e mod N ≡ c is equivalent to:
      m^e mod N = c mod N
      notice here we do use =, and not ≡

      We can think of mod as a function that takes some value and returns a result

      So this would be like writing:
      f(m^e)=f(c) where in our case f(x)= x mod N

      if we wanted to raise m^e to the power of d we could write:
      f((m^e)^d)=f(c^d)

      but since f(x)= x mod N this is the same as:
      (m^e)^d mod N = c^d mod N

      Which we can write in congruence modulo form as:
      (m^e)^d ≡ c^d (mod N)
      or as:
      (m^e)^d (mod N) ≡ c^d
      or if we understand that we are working in mod N as:
      (m^e)^d ≡ c^d

      Some people put brackets around the mod N, others don't.
      Personally, I prefer to use brackets around mod N, when working with ≡.

      Approach #2)
      mod N just describes the mathematical system we are using
      to perform our equations in.
      It isn't a term in one of our expressions.

      e.g. lets say I have a mathematical system called (odd or even world)
      where the result of all calculations are only odd, or even
      we could then write:
      2+3 (odd or even world) ≡ 17
      which basically says that in (odd or even world) the result of 2+3 is equivalent to
      the result of 17 (both are odd in our (odd or even world), so they are equivalent)

      (odd or even world) is just a reminder as to what system we were using to
      perform our calculations

      similarly:
      11+7 (mod 11) ≡ 7
      is just saying, that in our world we do all our calculations (mod 11),
      11+7 is equivalent to 7. (This is true since 11+7=18, 18 mod 11=7 and 7 mod 11=7)


      For more info check out the series on Modular Arithmetic:
      https://www.khanacademy.org/math/applied-math/cryptography/modarithmetic/a/what-is-modular-arithmetic

      Hope this makes sense
      (7 votes)
  • blobby green style avatar for user Anisha S
    I'm a little confused by this concept. Does this mean Alice can only receive a secret message from Bob? What if she wants to send him something? I might have understood it wrong, but it seems Alice is sending him an open lock so he can send her back a locked message which she then opens up to read.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Alice has an infinite supply of the exact same lock (which only Alice has the key to), so she lets anybody grab one of these open locks whenever they want to. This allows anyone to send a locked message to Alice.

      If Alice wants to send a message to Bob, then Bob needs to give Alice an open lock that only he has a key to.

      So, in practice, anyone who wants to receive messages advertises their locks publicly, so that anyone can grab one of their open locks.
      (6 votes)
  • piceratops ultimate style avatar for user angel
    what was the guys name at the beginning and what did he do?
    (4 votes)
    Default Khan Academy avatar avatar for user
    • leaf green style avatar for user K Odam
      Clifford Cocks. He thought up a way of creating a trapdoor function to be used in a public-key cryptosystem. As he worked for the UK's GCHQ, his work remained secret. The idea was later independently discovered and is known as the RSA algorithm.
      (2 votes)
  • winston baby style avatar for user raisa.fall2015
    could anyone explain to me how is this different to the diffie-hellmann key exchange?
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      RSA vs Diffie-Hellman key exchange (DH)

      How they are the same:
      -both rely on the Discrete Log problem being hard

      How they are different:
      -RSA requires factoring large primes to be hard, DH does not
      -RSA uses a public key for the sender and a private key for the receiver, but DH creates a shared secret between the two parties. Fundamentally RSA is a public key encryption scheme while DH is a key exchange scheme. That is RSA is designed to encrypt any message, where DH is devised to generate a shared secret (a key).

      In practice, they are both typically used so that both parties will end up with a key for a symmetric key cipher. RSA can encrypt the key as the message, and send it to the other party, while DH can use the shared secret to generate a key.
      (2 votes)
  • hopper cool style avatar for user Florian Melzer
    What exactly is the ciphertext space?
    (2 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      Message Space= The collection of all possible message we can send
      Key Space= The collection of all possible keys we can use
      CipherText Space= The collection of all possible ciphertexts we can generate

      Generally when Alice wants to send a message securely to Bob she does the following :
      -she picks a message from the message space
      -she picks a key from the key space
      -she encrypts the message using the key and the cipher, which generates a cipher text (this cipher text will be part of the cipher text space)
      -she sends the cipher text to Bob
      -Bob decrypts the cipher text (using the key) into message text (sometimes called plain text)

      Hope this makes sense
      (4 votes)
  • piceratops ultimate style avatar for user Isabelle Early
    Why do the equal signs have three lines instead of two?
    (2 votes)
    Default Khan Academy avatar avatar for user

Video transcript

- [Voiceover] The solution was found by another British mathematician and cryptographer, Clifford Cocks. Cocks needed to construct a special kind of one-way function called a trapdoor one-way function. This is a function that is easy to compute in one direction, yet difficult to reverse, unless you have special information, called the trapdoor. For this, he turned to modular exponentiation, which we introduced as clock arithmetic, in the Diffie–Hellman key exchange, as follows. Take a number, raise it to some exponent, divide by the modulus and output the remainder. This can be used to encrypt a message as follows: Imagine Bob has a message, which is converted into a number, m. He then multiplies his number by itself, e times, where e is a public exponent, then he divides the result by a random number, N, and outputs the remainder of the division. This results in some number, c. This calculation is easy to perform, however, given only c, e, and N, it is much more difficult to determine which m was used, because we'd have to resort to some form of trial and error. So, this is our one-way function that we can apply to m, easy to perform, but difficult to reverse. It is our mathematical lock. Now, what about the key? The key is the trapdoor, some piece of information that makes it easy to reverse the encryption. We need to raise c to some other exponent, say d, which will undo the initial operation applied to m and return the original message m. So, both operations together, is the same as m to the power of e, all raised to the power of d, which is the same as, m to the power of e times d, e is the encryption, d is the decryption. Therefore, we need a way for Alice to construct e and d, which makes it difficult for anyone else to find d This requires a second one-way function which is used for generating d, and for this, he looked back to Euclid.