[Cryptography] PGP -- Can someone help me understand something?

[Ray Dillinger]

On 08/08/2018 11:45 PM, Matt Maxson wrote:

> I don't understand.  Why can't that happen?  For example, if I have 10 +
> x = 50  (this can be replaced with any formula that has exactly one
> unknown), I can solve for X.  In my thinking, isn't the unknown in the
> equation simply the key?  Sure, the maths are more complex, but it
> should be a trivial issue to work backwards and solve for the key.
> 
> Thanks in advance for the help.



A start on understanding what the basic shape of the "trick" is:

https://en.wikipedia.org/wiki/One-way_function

The short answer is that there's a lot of math that's easy to do but
very very hard to undo.

The classic example is that multiplication is easy and factoring is
hard.  If I give you a number that's the product of two very very large
primes, it's really difficult to find the lowest one of those two
primes.  It's unambiguous; It's the only unknown; It's just very very
hard to find it.

You can take the brute force approach.  It looks like this:


LET FirstFactor = SquareRoot(Target)
LET SecondFactor = SquareRoot(Target)

If IsNotPrime(FirstFactor)
    LET FirstFactor = NextPrimeLower(FirstFactor)

While FirstFactor * SecondFactor != Target AND SecondFactor < Target
   If FirstFactor * SecondFactor < Target
      LET SecondFactor = NextPrimeHigher(Target/FirstFactor)
   Else
      LET FirstFactor = NextPrimeLower(Target/SecondFactor)
EndWhile

If FirstFactor = SecondFactor
   Print "$Target is the square of $FirstFactor (which is prime)."
If SecondFactor = Target
   Print "$Target is not the product of any two prime numbers."
If FirstFactor * SecondFactor = Target
   Print "$Target is the product of $FirstFactor and $SecondFactor."



But you may notice the brute force approach will take a lot longer than
just multiplying FirstFactor by SecondFactor.  Think for a minute about
how many numbers there *ARE* when you're talking about thousand-digit
numbers.  Compare it to the number of microseconds in the lifetime of
the universe times the number of atoms in the visible universe if you
want a yardstick in some terms that might be relevant.

It turns out that there are a couple of tricky methods of factoring that
do better than brute force, but none that are even close to being as
easy as multiplying.  The tricky factoring methods require multiplying
bigger numbers than you'd need otherwise, but it's still possible to do
a multiplication in an instant that you can't factor with more than
infinitesimal probability during the lifetime of the universe.

Anyway, all public-key cryptography is built on one-way functions like
this.

				Bear

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: OpenPGP digital signature
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20180810/e564a0eb/attachment.sig>