# Encryption & decryption of integers using modular multiplicative inverse and extended euclidean algorithm

I'm looking for a neat algorithm, which is capable of encrypting an integer to another integer and decrypting it again AND is secure.

When I was in university, my professor showed me an awesome way to encrypt and decrypt integers using the modular multiplicative inverse combined with the extended euclidian algorithm. We then combined it with a base base10 to base16 conversion to make it shorter.

Now I wanted to use that algorithm again and tried to reproduce it for a whole day, but simply can't remember and/or figure it out again. I tried using Google for research, but haven't found anything usable, or let's say only non-understandable stuff for a math noob like me.

So, what I'm looking for is something like this:

n = 12345678        // number to encrypt, whereas 0 < n < 16^6
k = ????????
m = ????????

// I can't remember the exact calculation,
// but if I'm not too mistaken, it should
// look very similar to this
i = n * k % m       // 1 - 8 digits

r = base10to16(i)   // 1 - 6 letters

// Now it should be possible to decrypt it
// again... and that's where I'm stuck,
// because everything I tried didn't result
// in the expected result (12345678), which
// may also be due to a wrong calculation in
// the first step...


Can someone lead a total math noob to the right directions? Some easy-to-understand online lectures would be nice as well.

• Actually, this method isn't actually secure; with 2 known plaintext/ciphertext pairs, you can recover a small set of possible $k$, $m$ values, one of which will be correct. If you make $k$ significantly larger, you might make the attacker require 3 known pairs – poncho Mar 12 '16 at 22:13
• @poncho Could you provide a simple example or maybe a source that explains it in an understandable way? I'd be very interested, because I was very sure that this approach is secure. (Note that it does only produce the inverse of a number and nothing more - no actual text or message.) – Marcello Mönkemeyer Mar 12 '16 at 23:18
• If you have a plaintext/ciphertext pair $p, c$ with $c = p \cdot k % m$ and another pair $p', c'$ with $c' = p' \cdot k % m$, then $p' \cdot c - p \cdot c'$ will be a multiple of $m$; factor it, and (unless it happens to be 0) that'll give you a short list of possible $m$ values. – poncho Mar 13 '16 at 2:52
• @poncho Very interesting and plausible. Thanks for the explanation. As you seem to have some knowledge in the field of cryptography, can you tell me about a simple yet secure algorithm to encrypt and decrypt integer values? If it's simpler to find a fitting algorithm for integers with a fixed length, that wouldn't be much of a problem too. – Marcello Mönkemeyer Mar 13 '16 at 11:55
• @FoxRider Please look into Format Preserving Encryption (FPE) for that. – Maarten Bodewes Mar 16 '16 at 1:22