Cryptography-Digest Digest #904, Volume #8 Thu, 14 Jan 99 07:13:12 EST
Contents:
Re: On the Generation of Pseudo-OTP (Patrick Juola)
Re: Metaphysics Of Randomness (Patrick Juola)
old crypt-technology (drobick)
Re: New Twofish Source Code Available (Bruce Schneier)
Re: On the Generation of Pseudo-OTP (Snowhare)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: On the utility of using Nulls ([EMAIL PROTECTED])
Re: Irish school kid encryption (Matt Davey)
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Irish school kid encryption (Matt Davey)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: On the Generation of Pseudo-OTP
Date: 13 Jan 1999 14:37:11 -0500
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On 13 Jan 1999 10:14:57 -0500, [EMAIL PROTECTED] (Patrick Juola)
>wrote:
>>>Not if you must use that algorithm to reproduce the number, as is
>>>required in Chaitin's algorithmic complexity theory. Reduction is one
>>>criterion and reproducibliity is another.
>
>>Not if the size of the *algorithm* isn't included in the size of
>>the ``compression.''
>
>I do not understand what you just said - and I did read your earlier
>comment in the same regard.
>
>I am sure you have read Chaitin's works - in fact, it might have been
>you who recommed him to me a year ago. Therefore I know your comments
>are not based on ignorance of his theory.
>
>Please elaborate on what you are saying. Chaitin claims that C is of
>order 10^3 or smaller (one was around 400) for his programs in his
>modified LISP, which is relatively small compared to numbers one might
>encounter when discussing randomness.
>
>BTW, with regard to your earlier comment - indeed he does include the
>Turing Machine itself in the calculation of algorithmic complexity. He
>built his own TM using his own modification of LISP, and IIRC the
>whole shooting match was of order 10^3 in size including a general
>program to demonstrate his theorems.
Exactly. That's 'cause he's doing it right. 8-)
Let me start by (formally) defining compression -- a function A
is a compression algorithm (for the string x) iff
0) A is an algorithm (see any decent text for definition of functions
vis a vis algorithms)
i) there exists another algorithm A' s.t. A'(A) is the identity
function (i.e. A is invertible).
ii) when given input string x, it produces output y.
iii) the length of y is less than the length of x.
Lemma 1 -- There does not exist a function X s.t. X is a compression
algorithm for all strings. Proof is immediate by the pigeonhole principle.
Lemma 2 -- For any string x, there is a compression function Y s.t.
Y(x) is a single bit.
Proof by construction : the following is such an algorithm
if (<input> == x)
output 1;
else if (<input> == 1)
output x;
else output <input>
("Ta daaaa!")
(In other words, Y(x) == 1, Y(1) == x and Y is the identity elsewhere.)
The traditional task of a compressor is to minimize the size of y --
more generally, to minimize the y::x ratio over a domain of interest.
Chaitin isn't interested in compression per se. First of all, the
algorithms he is interested in aren't usually addressed as functions
because they don't take input. I can coerce his work into the framework
above by noting that his "functions" are inputless (e.g. x is the
empty string) and y is the string whose complexity is to be determined.
More formally, Chaitin is studying the *de*compression program A'
such that A'(epsilon) = x.
And, furthermore, he's interested not in the size of epsilon (which
is trivial and uninteresting), but in the size of the algorithm A'.
Now, note that the function Y above yields a method for generating
the string x. Simply concatenate two programs -- one that outputs
the number 1, and then the function Y' that converts 1 into x.
*IF* x is a very complex string, then the function Y' will not
be smaller than the KC-complexity of the string x. So the size
Y' is bounded from below, even while x can be compressed to an
arbitrary degree by a sufficiently complex program.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Metaphysics Of Randomness
Date: 13 Jan 1999 15:46:01 -0500
In article <[EMAIL PROTECTED]>,
Douglas E.Denny. <[EMAIL PROTECTED]> wrote:
>R. Knauer <[EMAIL PROTECTED]> writes
>
>>One conclusion from these considerations is that a number that is
>>generated algorithmically, no matter what the algorithm might be, is
>>not a true random number - because such a number always has some
>>reason for its existence, a reason that you could possibly discover if
>>you worked at it long enough or hard enough. That is why only the
>>TRNG-based OTP cryptosystem is proveably secure - all other systems
>>have an underlying calculable reason behind their encryption schemes.
>>
>>That means that almost all of classical cryptography (the OTP being
>>the sole exception) is not about security but is about obscurity,
>
>There is an inbuilt falacy in this above statement.
>If your proposition above about any random number generated is not a true
>random number, (for whatever reason) then the OTP _cannot_ be an
>exception as its (random) key is normally derived from an algorithm.
Mr. Knauer's statement is incorrect -- although not for the reason
given. I'm not familiar with *ANY* implementation of the OTP
in which the random key is derived from an algorithm; the
usual method by which the random key is chosen involves tapping
into some non-algorithmic source of "randomness". The classic
example is, of course the (Sperry-Rand) table of random numbers
which actually involved a complex pinball-machine/roulette-wheel
to develop the numbers.
Anyone who claims to have an algorithmic method of generating an OTP
is selling snake oil.
But, on the other hand, the reason that the OTP is provably
secure is *NOT* because of some mystical property involving
''true randomness'', but by a simple assumption of statistical
equiprobability and uncertainty
If the key is at least as uncertain as the message, then it's
possible to develop a provably perfect encryption method based
on that key. The typical problem is that messages are usually
very long (and hence exceed the uncertainty of most keys rather
quickly).
-kitten
------------------------------
From: drobick <[EMAIL PROTECTED]>
Subject: old crypt-technology
Date: Wed, 13 Jan 1999 20:21:48 +0100
==============03B1080AD61E994C39E750DC
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Halli Hallo!
I search doc from old crypt-technology.
I have any crypt-mashine documentet see http://www.arco.de/~drobick
bye Joe
==============03B1080AD61E994C39E750DC
Content-Type: text/html; charset=us-ascii
Content-Transfer-Encoding: 7bit
<HTML>
Halli Hallo!
<P>I search doc from old crypt-technology.
<BR>I have any crypt-mashine documentet see <A
HREF="http://www.arco.de/~drobick/sas.html">http://www.arco.de/~drobick</A>
<P>bye Joe</HTML>
==============03B1080AD61E994C39E750DC==
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: New Twofish Source Code Available
Date: Thu, 14 Jan 1999 09:02:16 GMT
On Tue, 05 Jan 1999 12:21:59 -0500, Uri Blumenthal
<[EMAIL PROTECTED]> wrote:
>Bruce Schneier wrote:
>> We have new Twofish source code--reference C, optimized C, and
>> ASM--that reflects the improvements we've made.
>
>But no Java code improvements yet?
We've had Java since the beginning. It was one of NIST's submission
requirements.
Bruce
**********************************************************************
Bruce Schneier, President, Counterpane Systems Phone: 612-823-1098
101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
Free crypto newsletter. See: http://www.counterpane.com
------------------------------
Subject: Re: On the Generation of Pseudo-OTP
From: [EMAIL PROTECTED] (Snowhare)
Date: Thu, 14 Jan 1999 03:53:08 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Nothing above this line is part of the signed message.
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>On Wed, 13 Jan 1999 12:27:14 -0500, "Trevor Jackson, III"
><[EMAIL PROTECTED]> wrote:
>
>>Shielding? Against neutrinos? You cannot be serious! The 50% absorption
>>value for lead is 6 trillion miles or so.
>
>And therefore a netrino would not disturb the output, not unless you
>put it next to 10 million tons of chlorine isotopes.
That depends on the 'luminosity' of the neutrino beam. They are
starting to reach the point where experimental beams are hazardous
because even with only one neutrino in umpteen zillion interacting,
that is enough to be dangerous from the radiation exposure. But then,
they aren't exactly using portable generators - nor would people
be unlikely to notice that the entire general environment was
radioactive....
Would you believe there is now a project to map the interior of the
Earth using neutrinos?
Benjamin Franz
=====BEGIN PGP SIGNATURE=====
Version: 2.6.2
iQCVAwUBNp1qkOjpikN3V52xAQHTngP/ZdO+/PMwnP+5Fj2yAutkYB0SDqbYHnk8
woKKJCWr584H88ExQlXHyAacQz5R3aAt4+bsGcMpjIGQsWawifZNa04Cx1HDGmJ6
ijOAmpVUkRyuLuFUq1CFfcTFFClu5xuwQUnsyGRw9aDXdglyXTOd9vuPkgEUUwVk
VY587W5DSzc=
=atns
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Wed, 13 Jan 1999 22:21:25 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 15:09:50 -0600, Jim Felling
<[EMAIL PROTECTED]> wrote:
>> 2) what other properties besides normality would make an arbitary
>> real useful for cryptographic purposes?
>1) Easy to compute arbitrary digits
>2) proper statistical behavior in a local (not an absolute sense) -- e.g. given
>a number t which is normal to all bases this still does not mean that in the
>first 2^256 digits even a single 7 (base 10) occurs - since the normality is
>over the entire (infinite) set of digits of the number and the accessible digits
>to us may well not be well behaved for our purposes.
>3) Compact representation of the number.( so one can transmit the key
>conveniently and unambiguously)
>Of those #2 is the most difficult to achieve and the hardest to document
>appropriately.( The number, since it is normal is well behaved as to randomness
>in a global sense, but this does not mean any local set of values (however
>large) is cryptographicly appropriate.)
Can't the same things be said of a TRNG?
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: On the utility of using Nulls
Date: Thu, 14 Jan 1999 10:58:00 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> With apologies to Terry Ritter about writing off the use of nulls to
> improve security, I did avail myself of them in a current cipher
> implementation just completed. In particular, output is in base 22, using
> any 22 characters of the alphabet. Experience can prove that you are in a
> rut, or at least getting prejudiced against that you have not fully
> explored.
>
> To disguise the ciphertext from something using a standard alphabet, the
> unused four characters are scattered about within the groups. This is key
> dependent, so as too make it still more difficult, the nulls can be
> different.
>
> As an part of the function, also used in decryption input, unacceptable
> characters, other then the essential 22 used in encryption, are stripped
> away before the nulls are added. If not happy with the pattern of nulls,
> simply run it again. With a few tests, I should be able to properly set
> the null frequencies to somewhat match usual ciphertext letter
> frequencies.
>
> As an example of the process, consider these lines as it are stripped of
> the null characters and resalted with J, Q, W, and X, the defaults in the
> program:
>
> (asane ample qofth eproc esscw onsid erwtx hesel inesa sxita xrxes trjip
> pedof thejn ullch aract ersan jdres alted ithan dthed efaul tsint hqepr
> ogram)
>
> (ajsan eampl eofth epqro cxess conws idjer these qline sajsi tares jtrip
> pxejd jofth enull cjhar acter saqnd resal tedit handt hedef aults inthe
> progr ajm)
>
> Note that the passages may vary in length, as it is possible that
> sequential nulls will be inserted. A different key might have different
> nulls. Normally, this would be done to ciphertext rather than text were
> spaces are not important at all. As this process screws up normal text
> pretty badly, think of the difficulty of attacking nulled ciphertexts.
> --
Actual this would not add much protection if one assumes that
the attacker has a copy of the encryption decryption program
even if the 4 character choseen at ramdom independent of the
key used for the encryption. its affect would be (26!)/((22!)(4!))
number of combinations which is interms of entropy or bit
space about 13.86 extra bits. It might be nice however if one
could keep the method secret since its use could be harder to
detect.
David Scott
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Matt Davey <[EMAIL PROTECTED]>
Subject: Re: Irish school kid encryption
Date: Thu, 14 Jan 1999 10:40:44 +0000
Anthony Lineham wrote:
>
> I read a brief news article today about a 16 year
> old Irish school girl who recently won a prize at
> a science fair for designing an encryption
> algorithm
It's an impressive bit of work. After a work placement with Baltimore
technologies (www.baltimoreinc.ie) she continued work on an idea they'd
suggested. It's based on large primes, but is much faster than RSA.
Here's more detailed info from William White, at Baltimore:
Matt Davey
=============================
From: William Whyte <[EMAIL PROTECTED]>
To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
Cc: "'Michael Purser'" <[EMAIL PROTECTED]>
Subject: RE: IrishCrypto
Date: Wed, 13 Jan 1999 10:00:37 -0000
On Wednesday, January 13, 1999 8:08 AM, David Parkinson
[SMTP:[EMAIL PROTECTED]] wrote:
> >From the front page of today's Times <www.the-times.co.uk>
> As usual (technically) content free. Anyone know any
> technical details?
Yes, I do. It's based on work that Sarah did in Baltimore when
she was here on a student work placement last March. We've been
looking at algorithms based on 2x2 matrices for a while and
gave her the idea to see what she could do with it.
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.
That was our idea, anyway. I haven't had time to look at Sarah's
project in great detail so I don't know how far (or even whether)
she's taken it beyond where we had it.
Sarah, by the way, is level-headed enough to know that new public-key
algorithms only made you millions if you invented them in the Seventies.
Her real problem is trying to stop the journalists talking up the
stupid parts of the story while still emphasising that there's a real
story in there.
Cheers,
William
============================================================================
=
William Whyte, Senior Cryptographer, Baltimore-Zergo
Zergo & Baltimore Technologies merge in $55m deal !
The new company name will be "Baltimore"
See Baltimore at Stands 235 & 425
RSA Data Security Conference, 17-21 Jan '99
Baltimore Ltd, IFSC House, International Financial Services Centre,
Custom House Quay, Dublin 1, Ireland.
Tel. +353 1 605 4399 Fax. +353 1 605 4388
Email: [EMAIL PROTECTED]
Website http://www.baltimoreinc.com/
Baltimore - Global e-Security
From: William Whyte <[EMAIL PROTECTED]>
To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
Subject: RE: IrishCrypto
Date: Wed, 13 Jan 1999 11:26:27 -0000
On Wednesday, January 13, 1999 10:01 AM, William Whyte
[SMTP:[EMAIL PROTECTED]] wrote:
> That was our idea, anyway. I haven't had time to look at Sarah's
> project in great detail so I don't know how far (or even whether)
> she's taken it beyond where we had it.
(replying to own mail... this way lies madness)
In fact, Sarah made substantial contributions to the development of the
algorithm, finding a way of trading off key generation time against
encryption time and doing a lot of work on the proof of security. It's
very impressive.
William
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Thu, 14 Jan 1999 00:41:31 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 13 Jan 1999 23:00:09 GMT, Darren New <[EMAIL PROTECTED]>
wrote:
>> I would respectfully suggest that "Chaitin's Omega" is fairly well
>> compressed just like that.
>Except for those of us who do not already possess the decompression
>algorithm.
Any algorithmic reduction in the complexity of a number must be
represented as a decompression algorithm so that it can be faithfully
reproduced. But there is no algorithmic reduction possible for
Chaitin's Omega. Each of the bits is formally indeterminant.
If you were to do the actual experiments necessary to test each of the
Turing Machine programs that make up the calculation of Omega, you
would get a completely random number which according to Chaitin's
theory of algorithmic complexity could not be reduced by any formal
procedure (that would allow the number to be reproduced faithfully).
Or, you could work thru the various parameters of Chaitin's
exponential diophantine equation, all 200 pages of it, to determine
empirically the individual bits of Omega. He constructed that equation
such that each bit of Omega represents whether the corresponding
parameterization results in a finite or an infinite set of solutions.
That is how I understant it. If I am wrong, please tell me why I am.
But first, you need to read his papers so there can be no
misunderstanding of what it is he is actually saying. Don't rely on me
to represent his theory with perfect accuracy - you need to check it
out for yourself.
http://www.umcs.maine.edu/~chaitin/
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/
Also, see his book "The Limits Of Mathematics", which contains the
core papers on this topic.
Bob Knauer
"Since the politician never believes what he says, he is surprised
when others believe him."
--Charles De Gaulle
------------------------------
From: Matt Davey <[EMAIL PROTECTED]>
Subject: Re: Irish school kid encryption
Date: Thu, 14 Jan 1999 10:41:23 +0000
Anthony Lineham wrote:
>
> I read a brief news article today about a 16 year
> old Irish school girl who recently won a prize at
> a science fair for designing an encryption
> algorithm
It's an impressive bit of work. After a work placement with Baltimore
technologies (www.baltimoreinc.ie) she continued work on an idea they'd
suggested. It's based on large primes, but is much faster than RSA.
Here's more detailed info from William White, at Baltimore:
Matt Davey
=============================
From: William Whyte <[EMAIL PROTECTED]>
To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
Cc: "'Michael Purser'" <[EMAIL PROTECTED]>
Subject: RE: IrishCrypto
Date: Wed, 13 Jan 1999 10:00:37 -0000
On Wednesday, January 13, 1999 8:08 AM, David Parkinson
[SMTP:[EMAIL PROTECTED]] wrote:
> >From the front page of today's Times <www.the-times.co.uk>
> As usual (technically) content free. Anyone know any
> technical details?
Yes, I do. It's based on work that Sarah did in Baltimore when
she was here on a student work placement last March. We've been
looking at algorithms based on 2x2 matrices for a while and
gave her the idea to see what she could do with it.
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.
That was our idea, anyway. I haven't had time to look at Sarah's
project in great detail so I don't know how far (or even whether)
she's taken it beyond where we had it.
Sarah, by the way, is level-headed enough to know that new public-key
algorithms only made you millions if you invented them in the Seventies.
Her real problem is trying to stop the journalists talking up the
stupid parts of the story while still emphasising that there's a real
story in there.
Cheers,
William
============================================================================
=
William Whyte, Senior Cryptographer, Baltimore-Zergo
Zergo & Baltimore Technologies merge in $55m deal !
The new company name will be "Baltimore"
See Baltimore at Stands 235 & 425
RSA Data Security Conference, 17-21 Jan '99
Baltimore Ltd, IFSC House, International Financial Services Centre,
Custom House Quay, Dublin 1, Ireland.
Tel. +353 1 605 4399 Fax. +353 1 605 4388
Email: [EMAIL PROTECTED]
Website http://www.baltimoreinc.com/
Baltimore - Global e-Security
From: William Whyte <[EMAIL PROTECTED]>
To: "'[EMAIL PROTECTED]'" <[EMAIL PROTECTED]>
Subject: RE: IrishCrypto
Date: Wed, 13 Jan 1999 11:26:27 -0000
On Wednesday, January 13, 1999 10:01 AM, William Whyte
[SMTP:[EMAIL PROTECTED]] wrote:
> That was our idea, anyway. I haven't had time to look at Sarah's
> project in great detail so I don't know how far (or even whether)
> she's taken it beyond where we had it.
(replying to own mail... this way lies madness)
In fact, Sarah made substantial contributions to the development of the
algorithm, finding a way of trading off key generation time against
encryption time and doing a lot of work on the proof of security. It's
very impressive.
William
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
