[3962] in cryptography@c2.net mail archive
Re: Matrix based variant on RSA
daemon@ATHENA.MIT.EDU (Harald Hanche-Olsen)
Wed Jan 13 16:44:37 1999
To: cryptography@c2.net
In-Reply-To: Your message of "Wed, 13 Jan 1999 21:21:34 +0100"
<199901132021.VAA14297@replay.com>
Date: Wed, 13 Jan 1999 22:25:54 +0100
From: Harald Hanche-Olsen <hanche@math.ntnu.no>
- Anonymous <nobody@replay.com>:
| 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
| > [...]
|
| It is hard to understand how knowledge of the prime factors of n can
| help with matrix multiplications.
Indeed, but allow me to speculate for a moment. Finding the
eigenvalues of a two by two matrix requires extracting square roots,
and we know that finding square roots modulo an RSA number n is as
hard as factoring n. Thus, diagonalizing a 2x2 matrix modulo n is as
hard as factoring. Perhaps this could prove useful? I'll ponder this
while soaking in my (overdue) bath tonight.
--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- «There arises from a bad and unapt formation of words
a wonderful obstruction to the mind.» - Francis Bacon
