So How Do I Divide In Crypto Space?

So How Do I Divide In Crypto Space?

In cryptography, we typically only deal with unsigned integers and where are number can span to more than 4,096 bits. Our normal maths deals with 64-bits, but with cryptography, we have extremely large values, such as for 2,048 bits we get a maximum value of:

32,317,006,071,311,007,300,714,876,688,669,951,960,444,102,669,715,
484,032,130,345,427,524,655,138,867,890,893,197,201,411,522,913,463,
688,717,960,921,898,019,494,119,559,150,490,921,095,088,152,386,448,
283,120,630,877,367,300,996,091,750,197,750,389,652,1 06,796,057,638,
384,067,568,276,792,218,642,619,756,161,838,094,338,476,170,470,581,
645,852,036,305,042,887,575,891,541,065,808,6 07,552,399,123,930,385,
521,914,333,389,668,342,420,684,974,786,564,569,494,856,176,035,326,
322,058,077,805,659,331,026,192,708,4 60,314,150,258,592,864,177,116,
725,943,603,718,461,857,357,598,351,152,301,645,904,403,697,613,233,
287,231,227,125,684,710,820,2 09,725,157,101,726,931,323,469,678,542,
580,656,697,935,045,997,268,352,998,638,215,525,166,389,437,335,543,
602,135,433,229,604,6 45,318,478,604,952,148,193,555,853,611,059,596,
230,656

Common operators are “to the power of” and the modulus operator. We can also use the multiply operator in our maths, such as if we have of n and which is secret and a message value of M, the encrypted message is then:

Encrypted_Message = n x M

we often use the mod operator to hide the value of n that we have used, so it becomes:

Encrypted_Message = (n x M) mod p

and where p is a prime number and the mod operator is the remainder from an integer divide operation. If n is an extremely large value, it will take an adversary — Eve — a great deal of time to try all the values of n, and so our message is likely to be secure.

Now let’s take a simple example of n=5 and a message of M=17, and select a prime number of 67. The result will be:

Encrypted_Message = 5 x 17 (mod 67) = 18

We have to imagine that in real life that these values will be extremely large so that even if we know the result and the prime number (p), we cannot determine the n value within a reasonable time limit (as there are so many possible values). But let’s say that we know the value of n (our private key), how do we perform a divide?

Message = Encrypted_Result/n (mod p)

Well to solve this we perform an inverse n (mod p) operation. Then we just multiply the result to find the solution. The method used is the Extended Euclidean algorithm and the code used is:

def extended_euclidean_algorithm(a, b):"""
    Returns a three-tuple (gcd, x, y) such that
    a * x + b * y == gcd, where gcd is the greatest
    common divisor of a and b.

    This function implements the extended Euclidean
    algorithm and runs in O(log b) in the worst case.
    """
    s, old_s = 0, 1
    t, old_t = 1, 0
    r, old_r = b, a

    while r != 0:
        quotient = old_r // r
        old_r, r = r, old_r - quotient * r
        old_s, s = s, old_s - quotient * s
        old_t, t = t, old_t - quotient * t

    return old_r, old_s, old_t

def inverse_of(n, p):"""
    Returns the multiplicative inverse of
    n modulo p.

    This function returns an integer m such that
    (n * m) % p == 1.
    """
    gcd, x, y = extended_euclidean_algorithm(n, p)
    assert (n * x + p * y) % p == gcd

    if gcd != 1:
        # Either n is 0, or p is not a prime number.raise ValueError('{} has no multiplicative inverse ''modulo {}'.format(n, p))else:return x % p

For n = 5 and a prime number of 67 we get the following: [Try]

The inverse of 5 mod 67 is 27

Now we have an inverse value for n is 27. So let’s try:

M = 18 x 27 mod 67 = 17

and so we have found our original value. Within RSA we have the form of:

(e x d) mod PHI = 1

Let’s say we have a e value of 53 and a PHI of 120 [here] we get a result of 77. So if we try this we get:

(53 x 77) (mod 120)

and the answer is 1.

So there you go, we have achieved a divide operation using unsigned integration. We see this type of operation when we use El Gamal encryption [here], and in selected the decryption key in RSA [here], and I have used it here in a fair and honest voting system [here].