# How does two-key cryptography work?
**URL:** https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787
**Category:** Factual Questions
**Created:** [January 10, 2013, 8:04pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787 "2013-01-10T20:04:49Z")
**Posts on this page:** 9
**Page:** 1
### Author:  [@dstarfire](https://boards.straightdope.com/u/dstarfire)
#### Post date: [January 10, 2013, 8:04pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/1 "2013-01-10T20:04:49Z")
Is two key cryptography really as simple as multiplying two very large prime numbers to create a masterkey (just my term for it) that is then interlaced with the data (using and, xor, etc.)?
Or are there some other computations involved in generating the masterkey?
I got this after a comment in a Security Now podcast about elliptic curve cryptography (ecc). They talked about how the math for ecc is inherently complex, while RSA-style cryptography is relies on the fact that we’re just not very good at factoring products of large primes.
---
### Author:  [@ftg](https://boards.straightdope.com/u/ftg)
#### Post date: [January 10, 2013, 8:37pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/2 "2013-01-10T20:37:38Z")
The [method](http://en.wikipedia.org/wiki/RSA_(algorithm)) for RSA encryption is relatively simple to understand. Why the method works is not so easy, since you need to understand properties of Euler’s totient function and exponentiation/prime/mod stuff.
You definitely _don’t_ use XOR-type functions unless you are using something like one time pads, which for longish bits of data are not practical.
Note that people are generally sloppy about their language regarding RSA and factoring. A good factoring algorithm would break RSA, but breaking RSA is not known to provably require a good factoring algorithm. There might be some other way to break it. So its security doesn’t rely only on factoring being hard, but on no other exploit being known … for now … outside of the NSA.
---
### Author:  [@leahcim](https://boards.straightdope.com/u/leahcim)
#### Post date: [January 10, 2013, 8:40pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/3 "2013-01-10T20:40:29Z")
Not entirely. RSA does involve picking two very large primes, p and q, and then computing n = pq which is then publicly known, but it is more complex than just xor-ing or interlacing, or whatever.
What is done is:
[ol]
[li]Pick prime p and q, and compute n = p_q, publish n (but not p and q).[/li][li]compute phi = (p-1)_(q-1)[/li][li]Pick your encryption key e, such that gcd(e, phi) = 1[/li][li]Derive your decryption key such that de = 1 (mod phi)[/li][li]Publish e, keep d[/li][/ol]
Encrypting a message is just raising a number to e and taking the remainder modulo n and decrypting it is raising the result to d and taking the remainder modulo n. There is some math involved in proving that this all works.
If we could easily factor large numbers that are the product of two primes, than anyone with n (which is not kept secret) could figure out p, and q, and therefore phi, and solve de = 1 (mod phi) using the public e to solve for d. Which is bad.
---
### Author:  [@Punoqllads](https://boards.straightdope.com/u/Punoqllads)
#### Post date: [January 10, 2013, 9:08pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/4 "2013-01-10T21:08:43Z")
> [@dstarfire](#):
>
> I got this after a comment in a Security Now podcast about elliptic curve cryptography (ecc). They talked about how the math for ecc is inherently complex, while RSA-style cryptography is relies on the fact that we’re just not very good at factoring products of large primes.
Gah. Elliptic curve cryptography is very young, on the order of decades. No one’s come up with a way to compromise it _yet_, but there’s no guarantee that some [Ramanujan](http://en.wikipedia.org/wiki/Srinivasa_Ramanujan) won’t pop up with some method to break it. Prime factorization, on the other hand, has been literally studied for [millenia](http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) and though we’ve gotten [better](http://en.wikipedia.org/wiki/General_number_field_sieve) at it, we’re still not close to breaking it. And even if we do figure out how to break it, there’s still [discrete logarithm](http://en.wikipedia.org/wiki/Discrete_logarithm#Cryptography%5B/url) cryptography.
I’d argue that algorithms that are easier to understand are _stronger_ than difficult-to-understand algorithms, because they’re much easier to analyze for possible weaknesses.
---
### Author:  [@Derleth](https://boards.straightdope.com/u/Derleth)
#### Post date: [January 10, 2013, 9:48pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/5 "2013-01-10T21:48:03Z")
> [@leahcim](#):
>
> computing n = pq which is then publicly known
Which is why this is called ‘public-key cryptography’ in reference works. Search for that phrase to get a lot more useful information.
---
### Author:  [@KarlGauss](https://boards.straightdope.com/u/KarlGauss)
#### Post date: [January 10, 2013, 10:26pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/6 "2013-01-10T22:26:52Z")
> [@ftg](#):
>
> . . . for RSA . . . no other exploit being known … for now … outside of the NSA.
I am not sure if this a joke, a speculation, or, Gawd forbid, true.
---
### Author:  [@terentii](https://boards.straightdope.com/u/terentii)
#### Post date: [January 10, 2013, 10:35pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/7 "2013-01-10T22:35:54Z")
Freakin’ mathematicians just killed my interest in cryptography. :mad:
---
### Author:  [@leahcim](https://boards.straightdope.com/u/leahcim)
#### Post date: [January 10, 2013, 10:39pm UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/8 "2013-01-10T22:39:28Z")
> [@Derleth](#):
>
> Which is why this is called ‘public-key cryptography’ in reference works. Search for that phrase to get a lot more useful information.
Technically it is the pair (e, n) which is the public key (or (d,n), it doesn’t matter which one you pick). You can’t do encryption without both numbers.
[QUOTE=KarlGauss]
I am not sure if this a joke, a speculation, or, Gawd forbid, true.
[/QUOTE]
The statement is probably true. There is, as far as we know, no one outside of the NSA who can do this. No one’s making any claim about anyone inside the NSA 🙂 .
---
### Author:  [@Chronos](https://boards.straightdope.com/u/Chronos)
#### Post date: [January 11, 2013, 1:03am UTC](https://boards.straightdope.com/t/how-does-two-key-cryptography-work/646787/9 "2013-01-11T01:03:49Z")
All jokes aside, if there is anyone who has a crack for RSA, they’re probably in the NSA. But in all likelihood, they don’t have one either. Mathematicians (like most folks) like talking about their work, and if anyone had an algorithm for factoring large numbers (or anything else that would compromise RSA), it would probably be very hard to keep them quiet.