Discussion:
A proposed new algorithm
(too old to reply)
vernonner3voltazim
2004-10-30 04:38:34 UTC
Permalink
You may be aware that when you take the reciprocal
of a prime number P, its period often has length
P-1. Actually, if you try enough numerical Bases
(Base Two, Base Three, etc), you will ALWAYS fine
a period of P-1 in at least one Base, and often
many. (Meanwhile, composite number C never has
a period of C-1 in any Base.)

So you can take the reciprocal of some number on
the order of one hundred million, and Base Two,
and quickly and easily end up with a hundred
million pseudorandom digits. In fact, because
it is so easy, you can take reciprocals (or other
divisions) near-simultaneously with a whole bunch
of primes, and combine their results to get a
pseudorandom sequence which can approach the
perfectly random condition arbitrarily closely.

Then you use those digits for "one-time-pad"
encryption. I've written a program to try this
method, specifically to encrypt files. In theory
the program's encryption level starts at about
64,000 bits, and goes up from there. You can
find/study it at:
https://sourceforge.net/project/showfiles.php?group_id=122468&package_id=134066&
release_id=278616


I hope I haven't introduced any weaknesses in
implementing it. Let me know! Thanks!
David Wagner
2004-11-01 05:23:16 UTC
Permalink
Post by vernonner3voltazim
So you can take the reciprocal of some number on
the order of one hundred million, and Base Two,
and quickly and easily end up with a hundred
million pseudorandom digits.
Then you use those digits for "one-time-pad"
encryption.
This is insecure; it is easily broken with continued fractions.
I think this generator was dubbed the 1/p generator. As I recall,
I believe the 1/p generator was first broken in the following paper
(however, I do not have a copy of it handy to double-check).
L. Blum, M. Blum, and M. Shub. "A Simple Unpredictable Pseudo-Random
Number Generator", SIAM Journal on Computing, volume 15, pp.364-383,
May 1986.
There is a much stronger result: using the root of a polynomial
(e.g., the square root of the key, a random integer) is not secure,
either. See the following paper for the attack.
R. Kannan, A. K. Lenstra, and L. Lovasz. "Polynomial factorization
and non-randomness of bits of algebraic and some transcendental
numbers", Proc. ACM STOC 84, pp.191-200, 1984.
http://portal.acm.org/citation.cfm?id=808681
Peter Pearson
2004-11-01 05:24:21 UTC
Permalink
Post by vernonner3voltazim
You may be aware that when you take the reciprocal
of a prime number P, its period often has length
P-1.
[snip]
So you can take the reciprocal of some number on
the order of one hundred million, and Base Two,
and quickly and easily end up with a hundred
million pseudorandom digits.
[snip]
Then you use those digits for "one-time-pad"
encryption.
[snip]
This design is closely related to using a linear
congruential pseudorandom number generator to generate
a keystream. Boyar and Knuth showed this to be insecure.
(Google [ boyar knuth congruential ].) Therefore I would
not expect the proposed design to survive cryptanalytic
attack. (The Original Poster doesn't specify the security
requirements he expects the algorithm to fulfill, but
minimal respectability would require that the prime P
not be efficiently computable from any large sequence of
digits of its reciprocal.)

To fill in some details, a linear congruential PRNG
produces a sequence of pseudorandom values X[i] using
the relation X[i+1] = ( a*X[i] + b ) mod c, where a, b, and
c are parameters chosen by the algorithm's designer.
In computing the decimal digits of the reciprocal of P,
successive remainders map directly onto the X[i]: one
evaluates X[i+1] = 10*X[i] mod P, the biggest difference
being that the pseudorandom sequence that one takes from
this process is not the X[i] but rather the quotients found
during the "mod" operation.

So, while I haven't broken the propsed cipher, I hope I've
inspired caution . . . and maybe slowed down its adoption until
some Don Coppersmith comes along and gives it a whack.

--
Peter Pearson
To email me, make these substitutions:
nowhere -> spamcop, invalid -> net
Paul Leyland
2004-11-01 06:32:31 UTC
Permalink
Post by vernonner3voltazim
You may be aware that when you take the reciprocal
of a prime number P, its period often has length
P-1. Actually, if you try enough numerical Bases
(Base Two, Base Three, etc), you will ALWAYS fine
a period of P-1 in at least one Base, and often
many. (Meanwhile, composite number C never has
a period of C-1 in any Base.)
So you can take the reciprocal of some number on
the order of one hundred million, and Base Two,
and quickly and easily end up with a hundred
million pseudorandom digits. In fact, because
it is so easy, you can take reciprocals (or other
divisions) near-simultaneously with a whole bunch
of primes, and combine their results to get a
pseudorandom sequence which can approach the
perfectly random condition arbitrarily closely.
Then you use those digits for "one-time-pad"
encryption. I've written a program to try this
method, specifically to encrypt files. In theory
the program's encryption level starts at about
64,000 bits, and goes up from there. You can
https://sourceforge.net/project/showfiles.php?group_id=122468&package_id=134066&
release_id=278616
I hope I haven't introduced any weaknesses in
implementing it. Let me know! Thanks!
I assume you have read and understood the justly famous Blum Blum Shub
paper, where the authors introduced two random number generators. One
was shown to be trivial to break (via continued fractions) and the
other was shown to be as hard as factoring. Guess which one yours
resembles.


Paul
--
Hanging on in quiet desperation is the English way.
The time is gone, the song is over.
Thought I'd something more to say.
Nick Maclaren
2004-11-02 02:38:00 UTC
Permalink
Post by Paul Leyland
I assume you have read and understood the justly famous Blum Blum Shub
paper, where the authors introduced two random number generators. One
was shown to be trivial to break (via continued fractions) and the
other was shown to be as hard as factoring. Guess which one yours
resembles.
Well, yes, but both have a lot in common, and the security of the Blum,
Blum and Shub generator is usually overstated. In both cases (as in
others), the key question is WHICH parameters are known and which are
secret. The usual assumption is that the modulus is known, which is
what makes the multiplicative congruential and similar generators so
insecure.

If, for example, I use N multiplicative congruential generators,
return the XOR of selected bits, and you don't know N, the actual
generators or which bits, I think that you might have a job predicting
the sequence even given quite a lot of bits.

Also, I can break the Blum, Blum and Shub generator NOT knowing the
modulus if I have enough bits (the 2/3 power of the squence length).
This isn't a major weakness, but is enough to debunk the common myth
that this is an absolutely secure generator - I feel that it should
be regarded as a 'randomness expander'. If I recall, their paper
more-or-less says this, but in different words.


Regards,
Nick Maclaren.
vernonner3voltazim
2004-11-06 07:00:32 UTC
Permalink
Thanks for the replies, folks!

Now I may be mistaken in what I'm about to write,
but I'm not sure that you've sufficiently digested
the descriptions in the source code of the program.
Here's a page where I spelled out more details of
what the program does, to prepare itself to do
encryption, than in my original post above:
http://www.halfbakery.com/idea/Primary_20Cryption#1099120544

But here I'll try to present the process as it
scrambles a single byte of data:

Imagine an Array of a (approximately at least) a
thousand division "scratchpads". Each scratchpad
has a "random"ly chosen prime divisor (ultimately
depending on the Key File), and a "random"ly chosen
dividend. The longer the Key File, the bigger this
Array, up to 65536 scratchpads. Four of the
scratchpads have special Control functionality.

Before scrambling our byte, we fetch 2 bits (via
division) from one Control scratchpad, to decide
"how many times will we do everything else". Values
0, 1, 2, 3 are converted into values 1, 2, 3, 2.
So, the Main Event will always be done once, often
twice, and sometimes thrice.

Within the Main Event, a second Control scratchpad
gives us 2 more bits, which determine "how many
specific scramblings will be done to the byte".
Values 0, 1, 2, or 3 will cause 2, 3, 4, or 5
scramble operations.

For each scramble operation, the third Control
scratchpad is tapped to provide 16 bits, which
are used as an Index into the main Array of
scratchpads. The program knows exactly how
many elements (N) of the Array are actually being
used, so the Modulus N of that 16-bit number
becomes the actual Index value. The Array
scratchpad at that Index location is tapped
(performs division) for 8 bits of scramble-data.

With respect to each particular current scramble-
operation, a fourth Control scratchpad is tapped
for 3 bits of data. One of eight different
operations will be done to our data-byte:
rotation, addition, subtraction, or exclusive-OR
-- or those same operations in conjuction with NOT.

So, here is a possible sequence in more detail:
First Control data: 2 Main Events
First Main Event:
Second Control data: 3 scramble operations
Frist scrambling:
Third Control data: access Array[529]
Fourth Control data: Add the 8 bits
Second scrambling:
Third Control data: access Array[933]
Fourth Control data: XOR the 8 bits
Third scrambling:
Third Control data: access Array[149]
Fourth Control data: Subtract, then NOT
Second Main Event:
Second Control data: 4 scramble operations
First scrambling:
Third Control data: access Array[58]
Fourth Control data: XOR, then NOT
Second scrambling:
Third Control data: access Array[863]
Fourth Control data: XOR the 8 bits
Third scrambling:
Third Control data: access Array[276]
Fourth Control data: Rotate*, then NOT
Fourth scrambling:
Third Control data: access Array[537]
Fourth Control data: Add the 8 bits

*Rotations are limited. The scramble-data
will cause the data-byte to be circularly
shifted only 1-to-7 bit-positions.

We now save the scrambled byte, and fetch the
next piece of data for equivalent processing.

As you can see, while every Scratchpad
is indeed used for straightforward
division to yield some bits, only a
few bits are used at a time from any one
Scratchpad. If we have several thousand
bytes to process, then probably almost
every scratchpad in the Array will have
contributed to the overall scrambling,
by the time it's all done (and it DOES
go pretty quickly!).

I think, however, that what I have just
described is far more complicated than
can be handled by the cryptanalysis
methods so far mentioned in this Thread.

I could be wrong, of course. Let me know!
Thanks!
vernonner3voltazim
2004-11-08 01:43:08 UTC
Permalink
***@pinn.net (vernonner3voltazim) wrote:
Sorry, folks; I need to correct an error in
this description.
Post by vernonner3voltazim
Imagine an Array of a (approximately at least) a
thousand division "scratchpads". Each scratchpad
has a "random"ly chosen prime divisor (ultimately
depending on the Key File), and a "random"ly chosen
dividend. The longer the Key File, the bigger this
Array, up to 65536 scratchpads. Four of the
scratchpads have special Control functionality.
Before scrambling our byte, we fetch 2 bits (via
division) from one Control scratchpad, to decide
"how many times will we do everything else". Values
0, 1, 2, 3 are converted into values 1, 2, 3, 2.
So, the Main Event will always be done once, often
twice, and sometimes thrice.
While the preceding paragraph is quite true, I
left out something. Just before the scrambling
process begins, the data byte is saved in a local
variable. At the start of each loop controlled
by that first special scratchpad, the databyte is
restored from the saved copy. This is deliberate
and I'll explain below.
Post by vernonner3voltazim
First Control data: 2 Main Events
Second Control data: 3 scramble operations
Third Control data: access Array[529]
Fourth Control data: Add the 8 bits
Third Control data: access Array[933]
Fourth Control data: XOR the 8 bits
Third Control data: access Array[149]
Fourth Control data: Subtract, then NOT
As I wrote above, here is where the original
data byte gets restored.
Post by vernonner3voltazim
Second Control data: 4 scramble operations
Third Control data: access Array[58]
Fourth Control data: XOR, then NOT
Third Control data: access Array[863]
Fourth Control data: XOR the 8 bits
Third Control data: access Array[276]
Fourth Control data: Rotate*, then NOT
Third Control data: access Array[537]
Fourth Control data: Add the 8 bits
Since restoration of the databyte happens
at the beginning of each Main Event loop,
only the LAST loop ends up actually
providing the scrambled output that is to
be considered encrypted data. The deliberate
purpose is to BREAK UP even more, the sequential
usage of division data. That is, because it
is possible that Array[643] be "randomly"
selected in both the first and the second
Main Event, well, in that case the first
8 bits returned will essentially be wasted,
and only the second 8 bits will have helped
scramble the data. How is the cryptanalyst
going to know WHICH group of 8 bits is used,
FOR REAL, when half are (on the average)
"randomly" used and discarded?

As a minor challenge (perhaps to be modestly
funded, but as yet undecided), I'm thinking
of selecting some publicly available document
and scrambling it. The challange would be,
having both the plaintext and the ciphertext,
AND the source code of the CRYPTION program,
to figure out what (publicly available)
Key File and other data was used to do the
scrambling. After all, if that challenge
turns out to be sufficiently difficult, then
imagine the situation of the cryptanalyst
who only has the ciphertext and knowledge
of the algorithm!

Loading...