Modular Arithmetic One-Way Functions

Page #656 of Chapter: Crypto-for-the-rest-of-us

level indicator


Number theory is apparently rich with one-way functions, which may in turn reflect our lack of imagination, not any built-in mathematical reality.

Let's consider: Y = XZ mod n

Given any two from the set {X,Y,Z} it is possible to find the third

But at first glance, finding that third variable is difficult (intractable) regardless which is the unknown.

Interestingly enough we found an elegant mathematical shortcut to compute Y from {X,Z}, and found no similar "trick" to compute X from {Z,Y} or to compute Z from {X,Y}. Is it because we are not smart enough to find these shortcuts, or because they don't exist?

Cryptographers, being human, tend to the latter.

Here is the shortcut we found to computing Y from {X,Z}:

Suppose X=16243, Z =77, n=622.

Y = 1624377 = 5.21 * 10 400, which is way too large to write in the normal decimal format.

We discovered two useful theorems:

A*B mod n = (A mod n) * (B mod n)
(A+B) mod n = A mod n + B mod n

That allow us to easily compute large exponents from small exponents.

Here is what we do for the above example:

Y = 1624377 = 1624326+23+21 = (1624364)(162438)(162434)(16243)

And since 16243 mod 622 = 71, we may compute 714 = 493, and 718 = 4932 = 469, and similarly 7164 = 79
and conclude: Y = 1624377 = 5.21 * 10 400 = 79 * 469 * 493 * 71 = 29 mod 622

We found a shortcut that bypassed the need to exactly compute a very large number, and still achieve our goal (to find the value of this number modular 622). So far we did not find a similar short cut to compute either of the other two variables in this triumvirate. And we base our modern Internet security on the bet that such shortcut is not about to be found by the hackers around us.

* Version CE-H6703 (SERVER) Crypto Academy