I've been playing with the RSA cipher since it's announcement but
due to other interests have missed a lot of discussions of the finer
points. Thus I would like comments on the items in the list below.
I'm not a mathematician so rigorous proofs would probably be over my
head. I'll have to settle for consensus of opinions as to true/false.
My guess is these things are well known and of little consequence
but I'd like to hear from the experts that there is nothing of any
importance in these observations. In discusions of key generation,
for example, I've seen no reference to the possibility of deliberately
adjusting the ratio of p and q to weaken the key for an attacker.
Responses by private e-mail, please, unless there is something
here that would be interesting to the group. Thanks.
---------------------------------------------------
N/2 versus N (n=p*q, N=(p-1)*(q-1))
In the process of generating keys for RSA, the value N can be defined
as (p-1)*(q-1) and the encode/decode values e and d are computed
as d*e = (k*N)+1 where k is a positive integer. It appears N/2 always
works also. Thus d*e = (k*(N/2))+1 should always be valid.
k*n = a^2 - 1 (k times n equals a squared minus one)
For every n there is a positive integer 0 < k < n/4 such that k*n is
one less than a perfect square. There is another n/4 < k < n-2 which
is also one less than a perfect square.
E(m) = m (message enciphers as itself)
For every n there are at least 9 values of m (the message) where c (the
enciphered m) is equal to m for every valid e. m=0, m=1, and m=n-1 are
trivial. The others allow calculation of p and q.
search using add and test
There is a search method using a simple add and test-for-zero which
will find the factors in a fraction of n steps. While this is still
a very large number, the function is fairly simple in hardware. It can
be parallelized but probably not enough to be useful. Advances in
hardware, however, might make such a simple method possible.
-- ---------------------------------------------------------------------
| 73, E-mail | [EMAIL PROTECTED] |
| Lyn Kennedy webpage | http://webusers.anet-dfw.com/~lrkn/ |
| K5QWB pony express = P.O. Box 5133, Ovilla, TX, USA 75154 |
---Livin' on an information dirt road a few miles off the superhighway---