Cryptography-Digest Digest #967, Volume #9 Sun, 1 Aug 99 21:13:02 EDT
Contents:
Re: the defintion of Entropy ("Mark Hammer")
Error-Correcting Codes Added to Web Site
Re: Is breaking RSA NP-Complete ? ("rosi")
Re: A Thought or a Quoater ("rosi")
Re: How to keep crypto DLLs Secure? ([EMAIL PROTECTED])
Re: the defintion of Entropy ([EMAIL PROTECTED])
Re: How to keep crypto DLLs Secure? ([EMAIL PROTECTED])
Re: Help please (WWI/WWII ciphers) ([EMAIL PROTECTED])
Re: OTP export controlled? ("Dale Clapperton")
Re: (Game) 80-digits Factoring Challenge (Alwyn Allan)
Re: Is breaking RSA NP-Complete ? (Scott Fluhrer)
Re: Intel 810 chipset security ([EMAIL PROTECTED])
Re: The security of TEA (JPeschel)
The security of TEA ([EMAIL PROTECTED])
Re: bits and bytes ([EMAIL PROTECTED])
Re: (Game) 80-digits Factoring Challenge (JPeschel)
Re: What the hell is XOR? (Alan J Rosenthal)
Re: Modified Vigenere cipher (JPeschel)
----------------------------------------------------------------------------
From: "Mark Hammer" <[EMAIL PROTECTED]>
Subject: Re: the defintion of Entropy
Date: Sun, 1 Aug 1999 18:27:28 -0700
Sorry, but entropy assumes that the sequence is random.
--
Mark Hammer
[EMAIL PROTECTED]
http://free.prohosting.com/~maqua/
<[EMAIL PROTECTED]> wrote in message
news:7nvl9b$lu3$[EMAIL PROTECTED]...
> 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: Error-Correcting Codes Added to Web Site
Date: 1 Aug 99 22:02:47 GMT
Having finally found an intelligble description of the binary Golay code -
in a book on error-correcting codes by Vanstone and Van Oorschot*, two of
the authors of the Handbook of Applied Cryptography (!) - I've added a
section on error-correcting codes to my web page now that I could include
the things on it I wanted to.
It's at
http://www.ecn.ab.ca/~jsavard/mi0602.htm
and I wound up having to renumber the rest of the Miscellaneous chapter,
but in doing so, I found and fixed some bad internal links.
Other recent changes include: in the introduction, I give semaphore and
Braille as two examples of substitution. Marine signal flags, originally
present there for that purpose, have been moved to a page of their own, as
I had been adding so much fascinating detail on that subject that it was
an inappropriately long digression.
The flags are now at
http://www.ecn.ab.ca/~jsavard/flaint.htm
and you may also have noticed that the main page has been modified to give
the site a little bit of "pizazz"...but I hope that it also no longer
hurts anyone's eyes.
John Savard
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Sun, 1 Aug 1999 17:02:31 -0400
Dear Anton,
Bob might not be very specific, but there is no harm in reading more
on the subject.
Your points could be good ones, however I doubt if things were made
clear. This is no trivial stuff and too many questions could be asked and
need answers. Just an example, you seem, IMO, to draw some kind of
distinction between NP-hard and NP-complete, but I am not sure if any
reader is clear about the sense in which you are talking about the
difference.
Good to read the article you referred to (as well as all the places the
article quoted/referred to). I did, but I do not and can not claim to have
a full understanding of it. Somehow I doubt I ever will. Since you
mentioned that you know Brassard personally, you could perhaps go
to him directly and then give us, including Bob, a heads-up.
Please do not take it too much to your heart (for we are dealing with
a non-trivial monster). If you can 'relax' a bit, take my joke for a change:
If you think you truly understand the article you quoted,
you really do not. :)
--- (My Signature)
Anton Stiglic wrote in message <[EMAIL PROTECTED]>...
>Read the artcile before you start commenting this way on a news group:
>
> Brassard
> A Note on the Complexity of Cryptography
> IEEETIT: IEEE Transactions on Information Theory, Vol. 25, 1979.
>
>Comme back to this post once you have read it.
>
>
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: A Thought or a Quoater
Date: Sun, 1 Aug 1999 17:53:35 -0400
Thread lead gone. Attachment here after one in the thread.
=========================================================
Publish What Is Desired to Be Hidden
First, we take a look at OTP (one-time pad) 'by flipping it over'.
(Sorry one more time, but this time we have something new. We flipped
ourselves over! :))
When OTP is flipped over, we have OTM (one-time message). This is
nothing fancy, but a different 'orientation'. The pad is looked at as
a one-time message, while the XOR'd version with the real message,
which we regard in the flipped version as the pad, is the encrypted
version. The following tabulates the correspondence in the two
'orientations':
Conventional View Flipped Version
Pad (P) Message (M')
Message (M) Pad (P')
Ciphertext (C = P XOR M) Ciphertext (C' = M' XOR P')
It is really no different from the conventional way of looking at
them: pad as pad and message as message. However, it may be a bit
interesting looking at them 'upside-down'.
In the flipped version, even though when one gets M', one can get
nothing meaningful yet, as the 'message' is semantics full. It can be
interpreted in any way one wants. The way to interpret is determined
by 'determining' what P' to use for constructing the interpreter C'.
We now try a flavor, just a flavor though, of hiding something
that we publish. (If it looks silly to you, you'd better believe you
are right)
Let m[1] ... m[n] be n RSA moduli. For our convenience, say
512 bits. We send them, together with their order, openly to a
receipient. (Note that there is entity identification and other
issues, but for convenience, we simplify).
We execute a protocol (call it RSA-protocol in which we use the
m[i]) at the end of which bits are 'extracted' by the two parties
executing the protocol. E.g. we can index into the positions of
the bits to be extracted from each m[i] and the concatenated version
(of the extracted bits) is the established 'secret'. I am really
simplifying a lot, and the 'secret' can be a public key.
It is really laughable, but I am not advising doing such silly
things. I am illustrating through this example.
Now we look back and compare the RSA-protocol example and
the OTM notion, we can get something interesting perhaps.
With OTM, C' can not be sent in the open --- too obvious. With
RSA-protocol, the m[i] are semantics distinct. There is only one
way of breaking up the m[i] into prime factors --- public key is
public once we publish in this particular RSA-protocol. If we
combine the two, something different may appear:
The published thing reveals little (i.e. it can be
interpreted in many, many 'possible' ways). Before
the execution of the protocol, no attack is
meaningful. Now when the protocol starts, the
security depends on the underlying public-keying
scheme.
This concludes the fragments of a thought.
To repeat, I am not suggesting concrete solutions. 'Hiding
something that we publish' is in a special 'limited' sense.
Thank you very much.
--- (My Signature)
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How to keep crypto DLLs Secure?
Date: Sun, 01 Aug 1999 21:56:28 GMT
<snip>
Basically there is no security flaws with DLLs. You say that you
should have the functions (crypto) inside the .EXE but I can tell you
right now that is no more secure. Would it surprise you to know that
all .SYS, .DRV, .FNT, .386, .DLL and .EXE are executables? You could
just as well put the crypto in your fonts.
Basically any software can be infected by worms or viruses. PGP for
example can easily be broken by a worm that fixes all keys to a known
value. There are several solutions. 1) Stay off the net and check all
diskettes for 'anomalies'. 2) Build it your self (i.,e compile the
code) 3) Trust the builds. You could do trial encryptions and check
etc..
Each step is inherantly less secure. I for one trust the PGPi builds
since many people use them. I could have a virus in my copy and not
know it though ... (spooky). However I don't really use PGP much and
when I do it's for medium-secure (i.e private) messages only.
conclusion: DLLs are no less secure then EXEs if they are used
properly (clean the stack, clean the vmem and mem, a strong PRNG,
etc...)
Tom
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: Sun, 01 Aug 1999 21:59:56 GMT
In article <[EMAIL PROTECTED]>,
"Trevor L. Jackson; III" <[EMAIL PROTECTED]> wrote:
> No. "True Randomness" (soon to be a sequel to "True Lies") does not
> require infinite length. A single bit can be "truly random". The
> following bits from the same source do not influence the quality of
> randomness of the first bit.
>
What? Truly random bits are just that, bits. The period of the output
is infinite however (otherwise it's not truly random). You could for
example take 64 'truly' random bits and make a key for CAST. That
doesn't mean the period of the RNG is fixed or finite.
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: How to keep crypto DLLs Secure?
Date: Sun, 01 Aug 1999 22:05:09 GMT
In article <8n2p3.2595$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Dmitri Alperovitch) wrote:
> Obviously any machine code can be disassembled (whether it's
> DLL, EXE, or other executable code) and your encryption routines can
be
> disabled. But that doesn't compromise the security of your encryption
> algorithm. The attacker still will not be able to decrypt encrypted
text
> without access to encryption keys. It simply means that this
particular
> program that was "cracked" will not encrypt anything, but so what?
The only
> person who is going to suffer from this is the cracker and anyone who
he
> distributes it to (but you should already know better than download
programs
> from someone you don't trust).
I think he is aiming at authenticating binaries. DLL's obviously are
no less secure then .EXE files (or .fnt, .sys, .vxd, .386, etc...). I
could be sending a game which downloads updates which includes a virus
to disable PGP if it's found. Completely unrelated to PGP or security
but possible none the less. And unfortuneatly know one ever thinks of
that (it is covered in the PGP manual though).
Imagine if QUAKE (no offense to ID) had 'updates' with potential
viruses like that? Some viruses have been known to attack virus
scanners for example...
I think 'human' verification should be done. One could for example use
third party software to verify the software. Of course then you get
recursive virus clauses (attack the verifier). I think the only sound
solution would be to either trust the build or download from two
popular trusted sites and compare binaries. If one is different do not
trust either...
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: Help please (WWI/WWII ciphers)
Date: Sun, 01 Aug 1999 22:08:17 GMT
In article <KI0p3.1871$[EMAIL PROTECTED]>,
"Mike Blais" <[EMAIL PROTECTED]> wrote:
> If anyone can help me with this it would truly be appreciated, by me
and my
> girlfriend have spent far too much time on this and are ready to give
> up(this isn't really our type of stuff).
No one is perfect :)
> We have a package (newsletter) that has a code hidden in it, and our
only
> hint was that it was a code stolen from the Germans in the war(don't
know
> which war). Unless the code is actually hidden in the text this is
what we
> believe is the code: 223,172,926 paragraph 2 section (b)
and a
> page later
> 89,254,167 section (b) paragraph (iii)
> We don't know if the section/paragraph numbers mean anything but I
figured
> they should be included.
> So what I have is this 223 172 926 89 254 167 and the answer key is
like
> this
> ---- ------- ---------- --- ----
> As far as I found on the web the only number for letter cipher was
the
> Zimmerman Telegraph, but the key I found was in German. Also there
are more
> answer spaces than numbers and the only numbers in the rest of the
package
> are telephone numbers(all real)
> Any tips from whether we're on the right track to a solution would be
great.
Well I am no code breaker but...
The allies (more specifically mathematicians in britain) broke the
original and naval Enigma machines. Those might be what you are
looking for.
Happy hunting.
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: "Dale Clapperton" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OTP export controlled?
Date: Mon, 2 Aug 1999 08:33:29 +1000
[EMAIL PROTECTED] wrote in message <7o1j6f$slt$[EMAIL PROTECTED]>...
>In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>> [EMAIL PROTECTED] wrote:
>> > Well technically you have not supplied a key so it's still useless.
>>
>> The keys would be provided by the users, as with most computerized
>> encryption/decryption programs.
>
>But the key is the most important function in a OTP. In this case I
>would say sending the key would be a violation.
Oh right. So sending random data to someone is illegal?
pg9hekglhadf0g9h73q46knakldfb
Lock me up.
Dale
==================================================
Dale Clapperton J.P. (Qual.)
Manager, Blackbird Systems
http://www.uq.net.au/blackbird/
Add "DaleClapperton.asc" to website address for PGP Public Key
"The greatest threats to liberty lurk in insidious encroachment by men of
zeal, well-meaning but without understanding."
Mr Justice Brandeis, Olmstead v. United States, 277 U.S. 438 (1928)
------------------------------
Date: Sun, 01 Aug 1999 18:46:45 -0400
From: Alwyn Allan <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: (Game) 80-digits Factoring Challenge
Greg Keogh wrote:
> Just for your amusement, Mathematica 2.2.2 says:
>
> In[4]:=
> PrimeQ[256261430091697968103677033465028955910153603410170760238095478784430
> 33203276429]
> Out[4]=
> False
I used to like Mathematica, but I have retired my large body of code written for
it, and stop using it. The reasons are:
1) They do not tell you what algorithms they use internally. I could
occasionally get the answer by e-mail, but not always.
2) Version 2.2 crashes under Windows 95, and Wolfram refused to provide a
fix. They said to buy version 3.0. Even Microsoft does not compel you to upgrade
application software with OS versions. For years I kept a Windows 3.1 partition
just to run Mathematica.
-----------== Posted via Newsfeeds.Com, Uncensored Usenet News ==----------
http://www.newsfeeds.com The Largest Usenet Servers in the World!
======== Over 73,000 Newsgroups = Including Dedicated Binaries Servers =======
------------------------------
From: Scott Fluhrer <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Sun, 01 Aug 1999 22:47:23 GMT
In article <[EMAIL PROTECTED]>,
Safuat Hamdy <[EMAIL PROTECTED]> wrote:
>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).
Q: What's ZPP? Is it something similar to RP (randomized polynomial time)?
>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.
It's not junk, it just a bit imprecise. To make it precise, all you need to
do is replace the general "factoring" problem with the "has a factor less than"
problem (that is, given two integers (a, n), is it true that there exists two
integers (x, y) s.t. 1<x<a and x*y = n?)
"Has a factor less than" is a decision problem, and is polynomially equivilent
to the general "factoring" problem.
--
poncho
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Intel 810 chipset security
Date: Sun, 01 Aug 1999 19:33:29 -0400
> I would lone to see analysis of that and the PIII ID thingy. has
> anyone written software yet to emulate the instructions and fake ids
> yet?
www.bigbrotherinside.com has said that they have already created a program
that will allow you to randomize your ID (although I am not sure where to
get it). Intel says that if you turn it off, you cannot reenable the code
unless you reboot. They found a way around the reboot and did it
immediatly. It's all a bunch of BS. I personally am running a K-6 400
mHz, as I suggest everyone else do.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: The security of TEA
Date: 02 Aug 1999 00:19:50 GMT
>[EMAIL PROTECTED] writes:
>I just got through looking at the TEA algorithm. It's very easy to
>understand and very small. I am curious as to how secure the algorithm
>is (with 64 rounds).
You'll find a link to "Related-Key Cryptanalysis of 3-WAY, Biham-DES, CAST,
DES-X, NewDES, RC2, and TEA" in the "Algorithms and Attacks" page of my web
site.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED]
Subject: The security of TEA
Date: Sun, 01 Aug 1999 19:44:41 -0400
I just got through looking at the TEA algorithm. It's very easy to
understand and very small. I am curious as to how secure the algorithm
is (with 64 rounds). If I need a highly secure algorithm I'll use
something like blowfish or idea, but I am just curious as to how secure
this algorithm is. Thanks.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: bits and bytes
Date: Sun, 01 Aug 1999 19:37:17 -0400
I may be a little out of line here, but what does this have to do with
cryptography? Shouldn't this be taken to a different news group?
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: (Game) 80-digits Factoring Challenge
Date: 02 Aug 1999 00:33:53 GMT
>Jim Gillogly <[EMAIL PROTECTED]>writes:
>Good job, Graham -- Magma must have some good stuff in it.
I've been running a factoring program that purportedly uses the Pollard
Rho method. Am curious how long will it take to find a solution
on a Pentium 200.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (Alan J Rosenthal)
Subject: Re: What the hell is XOR?
Date: 2 Aug 99 00:27:28 GMT
[EMAIL PROTECTED] (John M. Gamble) writes:
>fungus <[EMAIL PROTECTED]> wrote:
>>void swap(int *a, int *b)
>>{
>> *a ^= *b;
>> *b ^= *a;
>> *a ^= *b;
>>}
>>
>>Will fail if a and b both point to the same int. Watch out
>>for hard-to-find bugs if you ever do anything like this.
>>
>But good heavens, why would you do it like that?
>
>/*
>** Swap via the three-xor method, contained in a single line.
>*/
>#define swap(a, b) (a ^= (b ^= (a ^= b)))
This has the identical defect. "swap(x,x)" sets x to 0.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: Modified Vigenere cipher
Date: 02 Aug 1999 00:50:05 GMT
> Jim Gillogly <[EMAIL PROTECTED]> quoted me when I wrote:
>> Fauzan Mirza wrote some code in C called vigsolve to solve
>> Vigeneres. I believe it also gives the IC for a couple other
>> polyalphabetic substitution systems.
>
by replying
>Period determination with I.C. is independent of the type of
>periodic polyalphabetic system: it measures the roughness of
>each column, but expresses no opinion on how that roughness
>came about. If it gives the IC for Vigenere it will also give
>it for Beaufort, Variant Beaufort, Porta, and the mixed alphabet
>versions.
>
Yes, thank Jim.
What I should have wrote was: Fauzan wrote some code in C
called vigsolve to solve Vigeneres. Later, he added code to display
the IOC. The program gives keys, according to F.M., for Vigenere,
Beaufort, and variant Beaufort ciphers.
Hope I got it right, this time.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** 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
******************************
