Re: real encryptor

-----BEGIN PGP SIGNED MESSAGE-----

Matt wrote:
>Karl Lui Barrus <klbarrus@owlnet.rice.edu> wrote:
>> The program I described earlier (RSA.tar.Z) is pretty minimal.
>> Secret keys are just text, not locked by a hash of a passphrase,
>> no "name" information attached.  Public keys are the same: no
>> username attached, no web of trust, etc.  The output is in
>> binary form, with no headers or checksums or anything.
>> PGP has keyrings, this program requires you to keep track of
>> seperate public keys on your own.
>Does this program exist?  If so where can I get it?

Sorry about the confusion Matt, I had sent a letter to Xenon about his
idea for stripped PGP describing this pure RSA program, and didn't
send it to the list.

Anyway, the program RSA.tar.gz is at ghost.dsi.unimi.it in /pub/crypt.
It implements pure RSA, no IDEA session keys, no MD5 hash of a
passphrase, no checksums, no keyring, no usernames, etc.  It is about
as minimal as you can get.  Which may be perfect for your purposes :-)

Because it is just RSA, it is SLOW!!  Which is to be expected, but all
the same the amount of time required to encrypt a reasonable sized
file is surprising.  Heck, even generating a decent size key takes
quite a bit of time.  I'm sure the code could stand some
optimizations, but even still public key crypto is much slower than
secret key.

Here's what a public key from the program looks like (in fact, it's my
public key for this program):

BB56AA026595006ED21C22FE5E5DD9432285846BB000627D0CFAA4FD28960EF2
33FABB5F35102460A001C7B2E37DE93C757C3935972086AD55BC69B36C438A05
291F3B75786BA0E4B9DBF43F6B5AE799A148D779303600D007449E258A8F3ABC
BA65393C0627BE386F9
#
B6E980C29F3D38C4898541565BCFE062AA50C60E4E411379143AD905E9A0257E
424FA4324B6D0BA71E6FBAC3C18D0F6A53D35CD7C3534DDB0D07ED642A8C7239
227DE4C742F141BCAE9698426E005F3F15B2E0AED6A0F125E69FC503B6057184
9124780B096F1C3ADE5

This public key and the associated secret key correspond to about a
700 bit modulus (100 digit and 110 digit primes).  The program encodes
numbers as an ascii string, but that is it.

The output of the program is the encrypted file, which has no header
or magic byte information, etc.  Decryption takes an encrypted file
back to the original form (except it looks like it pads and doesn't
toss the padding, maybe a bug) but if you use the wrong secret key
(i.e. not encrypted for you) the program decrypts the file to junk.
Or you can decrypt junk into different junk :-)  If you edit your keys
and change a few characters, or do the same to the encrypted file, you
don't get "checksum" errors, you just get an unreadable file.

Due to the slowness of the program, I think for testing the output for
randomness one should create relatively small keys (say 20 or 30
digits max) and encrypt large files.  Of course, at these sizes, it is
much easier to factor the modulus than brute force IDEA, for example.
Also, if you want larger keys be wary of the included script which
generates keys for you; it assumes you want a small key (and thus will
mess up the generated files).

So if indeed this is nothing but RSA then it should be impossible to
tell the output of the file from random noise.  (And incidentally, I
checked out Chaitin's Algorithmic Information Theory and have tried to
read the chapter on random numbers, but let's just say that it is
extremely slow reading :) I guess that's because it builds on stuff
from previous chapters or something...)

Karl Barrus
klbarrus@owlnet.rice.edu

-----BEGIN PGP SIGNATURE-----
Version: 2.3a

iQCVAgUBLVmLfoOA7OpLWtYzAQGpjwP+NmT5R3UlAbRN6A4YCk9DwqfjL1NlbhhQ
3ZDIqbRQISrrftcxNQv5doxUQNLKiQ2WaRBfQBuowCO3/mrjocsPK7QvA5P5on0R
N40uaudEpSCoEyem+DalRRKrrtSM9qfKNWxEQyL2OAI6cuw9zSvrXT+Ih9qtqigd
wKUju6ccoLM=
=Tsrs
-----END PGP SIGNATURE-----

> So if indeed this is nothing but RSA then it should be impossible to
> tell the output of the file from random noise.  (And incidentally, I
> checked out Chaitin's Algorithmic Information Theory and have tried to
> read the chapter on random numbers, but let's just say that it is
> extremely slow reading :) I guess that's because it builds on stuff
> from previous chapters or something...)
> 
> Karl Barrus

Chaitin's book is indeed tough sledding! For one thing, it's meant as
a monograph, giving his proofs in condensed form. (I assume Karl is
talking about "Algorithmic Information Theory.") And his two other
books are mostly collections of papers, articles, speeches, etc. Not
very pedagogically appealing. A more useful _text_ is the new "An
Introducution to Kolmogorov Complexity and Its Applications," by Li
and Vitanyi, 1993.

However, even this book will not help much in determining whether some
random block of numbers (no pun intended) is indeed "random." Most of
these results in Kolmogorov-Chaitin complexity are of an abstract
nature, not a _computational_ nature. That is, one doesn't find much
to help in determining if a number or set of numbers is random or not.

The best measures I know of remain the simple things like _entropy_,
but for "almost all" large enough blocks, the calculated entropy is
likely to be nearly maximal (e.g., 7.999... bits per ASCII character).

As interesting as I find K-C complexity and AIT in general to
be--especially in terms of things like why Occam's Razor works, how
induction and Bayesian statistics relate to the real world, etc.--I
can't say I've seen any ways in which it helps in cryptography or
crypanalysis.

--Tim May


-- 
..........................................................................
Timothy C. May         | Crypto Anarchy: encryption, digital money,  
tcmay@netcom.com       | anonymous networks, digital pseudonyms, zero
408-688-5409           | knowledge, reputations, information markets, 
W.A.S.T.E.: Aptos, CA  | black markets, collapse of governments.
Higher Power:2**859433 | Public Key: PGP and MailSafe available.