> William Whyte at Baltimore Technologies in Dublin --
> where Sarah Flannery worked recently and got a
> boost from the cryptographers there -- gave a brief
> rundown on her invention on mail list UKCrypto.
> There's a copy of his remarks at:
>
> http://jya.com/flannery.htm
There we find:
> The idea we were working on was to use 2x2 matrices with entries
> modulo n, n the product of 2 primes (ie an RSA number). The
> security is therefore exactly the same as the security of an RSA key with
> the same modulus. However, the encryption and decryption processes
> require only a small number of matrix multiplications rather than
> modular exponentiation, so both public-key operations (16 multiplications
> over the finite field) and private-key operations are as fast as a
> normal RSA private-key operation (17 multiplications). The downside
> is that both the key and the ciphertext are about eight times the
> length of the modulus, rather than more-or-less the length of the
> modulus as with RSA.
It is hard to understand how knowledge of the prime factors of n can help
with matrix multiplications. Knowing those factors is useful because it
tells you phi(n), the order of the exponential group mod n. But if there
is no exponentiation going on, of what use is knowing this group order?
You'd expect matrix operations to involve multiplication, division,
addition and subtraction mod n, but these can be done easily without
knowing its factors.
Are there examples of existing cryptosystems which benefit from RSA
moduli without using exponentiation?
