CODEWITHSUNDEEP
mathcryptography
Bill Joe
Bill Joe

Reputation: 61

Inverse within a finite field

I'm reading a book about cryptography (I've tried translate the terms from Spanish to English) and I don't understand how calculate the inverse within this field (originally the question used the term “body” instead of “field”, since that's a literal translation from languages like Spanish or German).

Encrypting with a monoalphabetic subtitution by pure decimation:

· Encryption: Ci = a* Mi mod n For example --> We will encrypt the letter C (C is the position 2, starting from 0) with a=20 and with the Spanish alfhabet (n=27) --> Ci = 20*C mod 27 = 20*2 mod 27 = 13 => N

· Decryption: a^(-1) * Ci mod n

HERE IS THE PROBLEM

a^(-1) is the inverse of the decimation factor in the body n; in other words: inverse(a, n). I've googled and tried to do some calculations but I don't obtain the correct result ---> inverse(a, n) = inverse(20, 27) = 16 (and the gcd is valid to do it).

For example:

22^(-1) * 13 mod 27 != 16

Upvotes: 1

Views: 4213

Answers (1)

Alex Riley
Alex Riley

Reputation: 176860

To find the modular (multiplicative) inverse in your example you have to find x such that (22 * x) % 27 == 1.

There are a variety of different ways you can do this mathematically. Note that in general, an inverse exists only if gcd(a, n) == 1.

If you want to write a simple algorithm for your example, try this Python code:

def inverse(a, n):
    for x in range(n):
        if (a * x) % n == 1:
            return x

This gives:

>>> inverse(22, 27)
16

>>> inverse(20, 27)
23

As mentioned in the comments below your question, there may well be better functions for computing the modular inverse in existing libraries for your favourite programming language.

Upvotes: 2

Related Questions