Cryptography-Digest Digest #960, Volume #9 Sat, 31 Jul 99 18:13:03 EDT
Contents:
Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a Byte?)
([EMAIL PROTECTED])
Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a Byte?)
(Eli Y. Orkman)
Re: With all the talk about random... ([EMAIL PROTECTED])
Re: the defintion of Entropy ([EMAIL PROTECTED])
Re: the defintion of Entropy ([EMAIL PROTECTED])
Re: With all the talk about random... ([EMAIL PROTECTED])
Re: OTP export controlled? (David Wagner)
Re: Chaffing and Winnoing ("rosi")
Re: Hash (One-Way) Functions (David C. Oshel)
Re: With all the talk about random... ([EMAIL PROTECTED])
Re: Looking for RC4 alternative (David Wagner)
Re: Is it possible to combine brute-force and ciphertext-only in an ("rosi")
Re: Hash (One-Way) Functions ([EMAIL PROTECTED])
Re: Is breaking RSA NP-Complete ? (Safuat Hamdy)
Re: Americans abroad/Encryption rules? (JPeschel)
Re: Knapsack Problem? TryIt! ("rosi")
Re: What the hell is XOR? (Xcott Craver)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.folklore.computers,alt.comp.lang.learn.c-c++,comp.lang.c++
Subject: Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a
Byte?)
Date: Sat, 31 Jul 1999 19:55:56 GMT
> Oh really. I'm using 5-bit baudot code on a 12-bit CPU with 6-bit
> characters. An 8-bit byte is useless to me. _*YOUR*_ definition of a
> byte is not, and never will be definitive. It is probably based on
your
> lack of experience with CPU architectures.
But most (around 90%) of public processors are octet based. Most
microcontrollers and desktop computers use that convention. For
example if you hooked up a serial port to your processor and a x86 what
is the length of a character? ...
> Simply becuase a term is "commonly used" does not mean it has a single
> interpretation. Indeed, commonly used terms are often the most easily
> overloaded. What does "format" mean? I know of at least five
> definitions, and am willing to bet my list is not exhaustive.
I think for the most part we can understand 'byte = octet'. For the
few cases it is not you can specify. I think it would be prudent in
any document to first specify what your definition of a byte is then
continue. Or simply use octet or '8x1 binary matrix' or 'numbers in GF
(256)' or ...
> "When I use a word it means exactly what I want it to mean, no more
and
> no less."
But 'byte' on a PIC and x86 may mean completely different things.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Eli Y. Orkman)
Crossposted-To:
alt.folklore.computers,alt.comp.lang.learn.c-c++,comp.lang.c++,microsoft.public.vc.language
Subject: Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a
Byte?)
Date: Sat, 31 Jul 1999 19:22:24 GMT
Okay, I'm sorry I fell for this silly troll. I realize now that you people
know perfectly well that a byte has eight bits, but you get some sort of
thrill from trying to start a stupid pointless argument about it. If you
want to continue this silly charade then argue among yourselves, because I
have better things to do.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: With all the talk about random...
Date: Sat, 31 Jul 1999 20:06:20 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Shktr00p1) wrote:
> >
> >When you have s, it's broken.
> >To turn it around, random() is as weak as it can possibly be.
> >To get that OTP, you need a real source of random numbers.
> >
> >/Kasper Pedersen
>
> I have written my random generator so that it is based on mouse
movement, time
> between clicks and mouse position. Is this effective?
probably not. You would still have to use a truly strong hash function
and lots of inputs. Note that an attacker could capture the mouse
movement so you have to assign something like micro-bit values to the
bit inputs...
Check out Yarrow for some ideas.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: the defintion of Entropy
Date: Sat, 31 Jul 1999 20:13:58 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Keith A Monahan wrote:
>
> > If that was an intuitive approach, I'd hate to see a non-intuitive
approach.
> >
> > Keith
> >
>
> The non-intuitive approach is realy more non-intuitive :)
>
But your first approach was wrong anyways.
What says ...00000000... (some inifite length bits) is more/less random
then ...1001110001... ?
If the period of the output is infinit then it's truly random and the
entropy in bits is inifite as well. Simple as that.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: the defintion of Entropy
Date: Sat, 31 Jul 1999 20:11:28 GMT
In article <[EMAIL PROTECTED]>,
Anton Stiglic <[EMAIL PROTECTED]> wrote:
>
> I have seen some bad usage of the word entropy, so I taught I'd post
the
>
> definition.
>
> There is two ways of considering entropy, one is mathematical
(through a
>
> set of axioms), the other is intuitive, I present the last one here:
<snip>
It's a lot easier then that. The entropy in bits of a sequence is the
number of bits required to represent the seqeunce. Truly random
sources have an infinite number of bits and thus total entropy. PRNG
algorithms have a finite number of bits and can be compressed if they
recycle. PRNG sequences can also be compressed to the PRNG state as
well. Like the output of a LFSR is 2^n - 1 bits long but you only need
n bits to re-create the sequence...
Simple no?
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: With all the talk about random...
Date: Sat, 31 Jul 1999 20:04:35 GMT
In article <7Vio3.362$[EMAIL PROTECTED]>,
"Kasper Pedersen" <[EMAIL PROTECTED]> wrote:
> The basic difference between the ones you get and the ones you need
(for
> encryption) is basically, that the ones you get from a PRNG (pseudo-)
are
> random for statistical purposes, but they aren't random AT ALL, while
the
> ones you get from a TRNG (hardware noise device) may not be good
enough for
> statistical purposes (bias, correlation), but they are random.
If there is a bias stronger then 1/2 over an infinite length seqeunce
it is not random. You can't say somethings random by looking at a
finite sequence cuz you will always find biases or some pattern that
may work for the section you have ...
All hardware sources are unpredictable at best, but not truly random.
> PRNG: Something that looks random, but is completely deterministic.
The only difference between a PRNG and a TRNG is that PRNG are finite
in nature and thus can never be 'truly' random.
> Look at a series of numbers: 01 07 49 43
> It will repeat (next is 01 again) because what I've written is just
> s:=(s*7) mod 100.
>
> The random() generator used in Borland C++ is
> s:=(s*134775813+1) mod 2^32
> When you use it in the form random(256), you get the most significant
8 bits
> of s.
> To crack a junk-OTP with this generator, I'll guess a single letter,
maybe
> 'e'?
> Then there are 24 bits left. The simplest is to run through 16M
> possibilities, it takes less than a second per character. Assuming
there are
> 20-non-'e' letters before the 'e', I have to wait 20 seconds for it
to crack
> (checking that the output is ascii characters).
>
> When you have s, it's broken.
> To turn it around, random() is as weak as it can possibly be.
> To get that OTP, you need a real source of random numbers.
In this case you could simply guess the 32-bit seed and check it
against the message.
Some must note that what doesn' look random to the 'eye' might actually
be random in nature (or unpredictable, or infinite ...). a million
zeros in a row is just as random as 1010101110111000011010010011 etc...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: 31 Jul 1999 13:16:31 -0700
In article <[EMAIL PROTECTED]>, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> Or else, the regulators would have to assert that the sample code
> *does* run afoul of the regulations, and I think they'd look
> rather silly trying to defend that in court.
That hasn't stopped them in the Junger case, where they asserted
in court exactly that a one-line OTP program is export-controlled
(if I'm not mistaken).
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Chaffing and Winnoing
Date: Sat, 31 Jul 1999 15:55:39 -0400
Dear Gabriel,
RSA for bulk data encryption is not just theoretical. However,
practical or not depends very much on individual's definition.
Hope this may help answer your first question(s).
--- (My Signature)
Gabriel Belingueres wrote in message <[EMAIL PROTECTED]>...
>Hi,
>
>Does anyone has tryed "chaffing and winnoing"? This is practical at all
>or is something theoretical only?
>
>Also, there is any SSL or TLS implementation using this schema as a
>Ciphersuite?
>
>Thanks,
>
>Gabriel
>
------------------------------
From: [EMAIL PROTECTED] (David C. Oshel)
Subject: Re: Hash (One-Way) Functions
Date: Sat, 31 Jul 1999 15:44:42 -0500
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
> Ok, I have a question:
> I am not sure about MD5, but SHA can take an input of over 1000
> characters long. The digest of this input is only 20 characters
> long...now if these algorithms have very few collisions, how is it
> possible for a inputs over 1000 characters long to all have a unique
> hash only 20 characters long?
The idea is, one input produces one output. If the output is 20
characters, that is 20 ch * 8 bits/ch or 160 bits, which represents a
binary number in the range 0 to 2^160 ("two to the 160th power"). The
number 2^160 exceeds the expiration date of the universe measured in
seconds, or something else that silly. Remember that 2^64 bankrupts the
rajahs, in the famous story of the rice grains and the chessboard.
This suggests that every document ever written on earth (including first
drafts and lost editions from the burned libraries of Alexandria) can be
enumerated by integers selected from the range 0 to 2^160.
The hash does not somehow encapsulate or include all the information the
source contains, it just indexes the source. The probability that two
sources will produce the same index is vanishingly small, but not
inconceivably small, if the hash is good: It plucks a number from a vast
pool of possible numbers, which is easy, while anyone trying to duplicate
the feat must pluck that *particular* number from the same vast pool,
which is nothing like easy.
If I understand what you're asking, that's approximately the answer.
--
David C. Oshel http://pobox.com/~dcoshel
Cedar Rapids, IA [EMAIL PROTECTED]
``Tension, apprehension and dissension have begun.''
-- Duffy Wyg&, in Alfred Bester's _The Demolished Man_
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: With all the talk about random...
Date: Sat, 31 Jul 1999 19:58:22 GMT
> Real random numbers are produced by rolling dice or equivalent
> methods.
Those are not random either. Consider physics your algorithm...
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Looking for RC4 alternative
Date: 31 Jul 1999 13:39:59 -0700
In article <7nt2ss$fc5$[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
> In the line:
> t = (S[i] + S[j]) mod 256
> the 'a+b' operation could be replaced by 'a-b', 'b-a' or
> 'a XOR b' with presumably the same result.
I'm not sure this is a good idea. All of your proposed alternatives
have the property that t=0 when i=j; this is not true of the original
RC4, and might make some attack slightly easier (I don't know). More
analysis would seem to be prudent before making this change.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Is it possible to combine brute-force and ciphertext-only in an
Date: Sat, 31 Jul 1999 16:23:13 -0400
wtshaw wrote in message ...
>In article <7ma58a$tfk$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>>
>> If the message was truly random you would not need to encrypt it would
>> you?
>>
>
>It might, for no other purpose, help drive an attacker mad. And, you
>would have a difficult time convincing someone who *wanted* to know that
>it was just nonsense and you were not hiding anything.
Beautiful. Then it is 'complete'.
>
>Consider that look-ahead in solving ciphertexts is pretty much like
>driving in a dense fog, it helps to know the road in advance if you don't
>want to run off into a ditch.
>
>Knowing that attackers will grasp at straws, the user can easily steer the
>unsuspecting to lose the correct way, if you have the deviousness to do
>so, after all, smoke and mirrors, lies and deception, are the stuff of
>good mind-game crypto.
>--
>Rest sometimes allows you to find new things to worry about but should give
you the patience to do something about them.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hash (One-Way) Functions
Date: Sat, 31 Jul 1999 20:58:32 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> > Ok, I have a question:
> > I am not sure about MD5, but SHA can take an input of over 1000
> > characters long. The digest of this input is only 20 characters
> > long...now if these algorithms have very few collisions, how is it
> > possible for a inputs over 1000 characters long to all have a unique
> > hash only 20 characters long?
>
> It isn't.
Good answer.
Well there are two attacks against a hash. These are unsolvable as
well so they are used as upper bound security models. There is a brute
force which means if I gave you A = H(M1) finding another hash such as
B = H(M2) would require on average 2^n-1 steps. (n = bits in output).
Then there is the birthday paradox attack. If I choose M1 and M2 at
random I should find A=B in 2^n/2 steps on average.
MD5 is reasonably secure against the former but not the later. So is
SHA.. SHA-1 is still believed to cling to the upper bound.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Free PRNG C++ lib:
'http://mypage.goplay.com/tomstdenis/prng.html'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Safuat Hamdy <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: 31 Jul 1999 23:07:53 +0200
Anton Stiglic <[EMAIL PROTECTED]> writes:
> But factoring is still not NP-Complet....
Is this what YOU think (or whish) or can you really prove it?
All the public knows (to my knowledge) is that COMPOSITES is in NP n co-NP
(well, ok, we know that PRIMES is in ZPP, and since PRIMES = co-COMPOSITES
and ZPP is closed under complement, COMPOSITES is in ZPP).
Everything else is conjecture, i.e. it is widely believed that COMPOSITES
is NOT NP-hard.
And PLEASE everybody recall that classes like P, NP, PSPACE and so on refer
to DECISIONAL problems ("does some property hold on some object", i.e. "is some
word in a particular set?"), hence in a precise sense a statement like
"factoring is (not) NP-hard" is simply junk.
--
S. Hamdy | All primes are odd except 2,
[EMAIL PROTECTED] | which is the oddest of all.
|
unsolicited commercial e-mail | D.E. Knuth
is strictly not welcome |
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Americans abroad/Encryption rules?
Date: 31 Jul 1999 20:51:08 GMT
>(W.G. Unruh) writes:
>You are just not allowed to take out of the USA any program which could
>create such an encrypted email
Bill, that's strange. When was the "personal use exemption" taken off the
books?
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Knapsack Problem? TryIt!
Date: Sat, 31 Jul 1999 15:51:20 -0400
Dear Vladirmir,
Good thoughts.
Only glanced at yours after being away from the group for a couple of
weeks. My impression is that you are beating on the beaten track. You
_may_ read, for things going 'your direction', Schnorr and Hoerner on
attempting at Chor-Rivest.
Thanks
--- (My Signature)
Vladimir Zabrodsky wrote in message <7npb29$ddj$[EMAIL PROTECTED]>...
>Hello,
>could you read my article "Does it make sense to solve the knapsack
>problem? TryIt!", please? See:
>
>http://www.geocities.com/SiliconValley/Garage/3323/knapsack.html
>
>Abstract: There are many variations of the knapsack problem; we
>consider only a simple one dealing with one-dimensional items: Given an
>array of positive integers A[1], ..., A[N]and an positive integer C
>find a subset of A[1], ..., A[N] that sums to C. An particular case of
>the knapsack problem is the partition problem: Given N positive
>integers, is there a way to partition the integers into 2 disjoint
>subsets so that the sum of the integers in each of the two subsets is
>equal?
>We can read in literature:
>The only known solution is brute force: test all possible subsets until
>the sum is found or you run out of subsets. When you have partition
>items from an office, i.e. for N (approximately) equals 100, it doesn't
>make sense to solve by WORLD'S FASTEST COMPUTER.
>
>I introduce a simple algorithm TryIt!; while an array A will contain
>really values of items (about 500 values of items from office or garage
>or hangar or dock) then the problem can be solved ALMOST ALWAYS only by
>the Rexx INTERPRETER and an ORDINARY PC in a REASONABLE amount of time.
>---------------------
>Thanks advance. I am looking forward your comment.
>Vladimir Zabrodsky
>CKD Blansko a.s., Gellhornova 1, Blansko 678 01, Czech Republic
>[EMAIL PROTECTED]
>http://www.geocities.com/SiliconValley/Garage/3323
>
>
>Sent via Deja.com http://www.deja.com/
>Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: What the hell is XOR?
Date: 31 Jul 1999 21:30:08 GMT
>>#define swap(a, b) (a ^= (b ^= (a ^= b)))
>swap(i,i).
>
>Oops.
>
>Even if *you* don't do it, someone else will.
Especially considering that someone's bound to use it in a sort,
or some code in which array elements are swapped iteratively;
All it takes is a tiny bounds overrun to zero out everything.
Or an algorithm which swaps indiscriminately, such as some variants
of selection sort. Not that you'd use selection sort.
But then, there are plenty of good hacks, which I wish people
would use more. And it still matters today in this age of
fast CPUs and fast disks, because it's also an age of streaming
media. Especially especially since a lot of the people with the
knowledge of image/signal processing to do it right are more EE
than CS, and less likely to know tricks which could give them
big-time speedup.
> Steve
-Caj
------------------------------
** 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
******************************
