Modular Multiplicative Inverse

Hi,

I'm trying to code the RSA algorithm in lua. Now, after hours i have problems with generating the Private key.

The step is: "Compute d, the modular multiplicative inverse of e (mod φ(n)) yielding"

How should i do this in Lua? I tried around with some Code, bit everytime i got wrong results. :(/>

Take a look at this stack exchange post. It explains things quite a bit more clearly than the Wikipedia if you are unfamiliar with some of those math terms.

Meanwhile I got it working by bruteforcing:

function modInverse(a,m)
  a = a % m
  for x = 1, m do
	if (a * x) % m == 1 then
	  return x
	end
  end
end

I translated it from C++ from here.
But this function is A: inefficient, B: it's not even able to generate 32bit Keys without crashing because it takes too long.

Now I'm trying to translate the other functions on this page. Im not that good at C++, so might someone explain what "pair<int, pair<int, int> >" means?

pair<int, pair<int, int>> is like a table {something, {something, something}}
make_pair(b, make_pair(xLast, yLast)) is like {b, {xLast, yLast}}
x.second.first is like x[2][1]

In Lua you wouldn't actually need the inner table.

Okay, now I got different code working:

function egcd(a, B)/>
	if a == 0 then
		return b, 0, 1
	else
		g, y, x = egcd(b % a, a)
		return g, x - (math.ceil(b / a) - 1) * y, y
	end
end

function modinv(a,m)
	g, x, y = egcd(a, m)
	if g ~= 1 then
		error("modular inverse does not exist")
	else
		return x % m
	end
end

It works very good and fast with generating up to 48bit RSA-Keys, but it makes errors with 56-bit-Keys (one ore some digits are wrong calculated) and when I try to generate 128-bit keys, it crashes with the error message in the second function. Does someone know why this could happen?

Here are examples:

32-bit: modinv(65537,1792011760) - function: 1137216673 - correct: 1137216673 - Correct!
48-bit: modinv(65537,121444194924000) - function: 56953893693473 - correct: 56953893693473 - Correct!
56-bit: modinv(65537,32478974171940912) - function: 2916997146284453 - correct: 7176526618305329 - Wrong!
128-bit: modinv(65537,158237197426104200175876099804099312720) - "abc.lua: 13: modular inverse does not exist"

btw: that "/>" at the first function is a bug in the forum software, I can't delete it, so ignore it.

luaj uses java doubles, 64-bit IEEE floating points, for all numeric values. When used to hold integers, this gives an effective limit of, I think, 52 bits? So that fits, 32 or 48 should work, anything bigger will not. You won't be able to represent an arbitrary 128-bit integer value in lua accurately, so you'll have to break them down into 4 32-bit values.

Note, this doesn't just apply to calculating with them; anything bigger than that as a constant value in your code will not even compile correctly to bytecode without losing the low bits.