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.
The method 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.
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 = pq, 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.
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 won’t pop up with some method to break it. Prime factorization, on the other hand, has been literally studied for millenia and though we’ve gotten better 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 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.
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 .
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.
.