Cryptography-Digest Digest #564, Volume #14 Fri, 8 Jun 01 07:13:00 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Vincent Quesnoit)
Re: Algorithms ("Tom St Denis")
Re: MD5 for random number generation? ("Tom St Denis")
Re: Notion of perfect secrecy ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("Tom St Denis")
Re: Simple C crypto ("Tom St Denis")
Re: Simple C crypto ("Tom St Denis")
Re: Simple C crypto ("Tom St Denis")
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large Primes
("Tom St Denis")
Re: RSA's new Factoring Challenges: $200,000 prize. ("Michael Brown")
Re: Simple C crypto ("Michael Brown")
----------------------------------------------------------------------------
From: Vincent Quesnoit <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 11:29:17 +0200
Reply-To: [EMAIL PROTECTED]
Tim Tyler a écrit :
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : I was referring to the following that you wrote previously:
>
> : Yes it is. Consider BICOM for example. It can map a
> : 8 bit cyphertext to one of some 2^128 plaintexts -
> : considerably more than your figure of 2^8.
>
> : Does the 2^128 come from using a 128 bit key for the
> : AES in it and there are 2^128 possible keys for AES?
>
> Yes.
I am puzzled, I thought AES was a block cypher which could not produce a
cypher text smaller than its own blocksize. Do you mean that AES can
decrypt one byte and produce a 16 byte output ?
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Algorithms
Date: Fri, 08 Jun 2001 10:37:25 GMT
"abhijeet" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Hi,
> I am writing my thesis on cryptography in Digital signature.
> Can anyone suggest me of any book or paper where I can get
> the full C or C++ code for the algorithms.
> thanking you
> regards
What algorithms?
Get
Applied Cryptography -- Bruce Schneier
Handbook of Applied Crypto -- CRC Press
A Course in Number Theory and Cryptography -- Neal Koblitz
and you will be all set
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: MD5 for random number generation?
Date: Fri, 08 Jun 2001 10:39:43 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
> :> :> Tom St Denis <[EMAIL PROTECTED]> wrote:
> :> :> :> Toby Sharp wrote:
>
> :> :> :> > I've heard of people using MD5 for random number generation.
But,
> :> :> :> > as far as I can tell, MD5 is a one-way hash algorithm. How is
> :> :> :> > this used for random numbers? [...]
> :>
> :> :> : Yeah, you have to make sure though, that your PRNG is forward and
> :> :> : backwards safe. [...]
> :>
> :> :> So you could just use
> :> :>
> :> :> : H[i] = HASH(SEED || i)
> :> :>
> :> :> : Which is essentially a CTR mode of operation.
> :> :>
> :> :> It looks like you're thinking of state compromises that don't affect
> :> :> SEED.
> :> :>
> :> :> If you think SEED might also be compromised, backward secrecy is
> :> :> hardly possible (without a source of entropy anyway) - and the
> :> :> second equation offers no forward secrecy.
> :>
> :> : Here's a tip. Give some thought to what you post.
> :>
> :> : No PRNG is ever secure if the initial seed is compromised. The seed
is
> :> : what determines the PRNG output...
> :>
> :> Security in the face of state compromise is a very important part of
> :> what forward secrecy in RNGs is all about.
>
> : Yes. And my PRNG I proposed is forward secure.
>
> : H[i] = HASH(SEED || I)
>
> : Suppose you guess H[i], how do you get H[i+1] or H[i-1]?
>
> You don't.
>
> However, say someone breaks into your office and wanders out with i and
> SEED.
>
> With this information they have access to all the past outputs of the RNG.
>
> This is known as a "backtracking attack" - and can be of significance if
> the RNG is used for key generation - since you don't want numerous past
> keys to be compromised by a single lapse of security on some future date.
>
> Backtracking attacks can be prevented - they are not inherent in all
PRNGs.
Which is why (if you well I dunno, ... er ... um READ MY ENTIRE POST) would
have found that I said you should reset the seed whenever you make a new
key. That way "wandering into the office to get SEED" will be a useless
venture.
> :> As for backward secrecy - this is (as I mentioned) impossible in a PRNG
> :> whose state has been compromised. However, the OP never mentioned
PRNGs.
>
> : Are you sure? Read the subject line!
>
> I see an R, an N and a G there - but can see no sign of a P.
>
> While concealing the forward evolution of a PRNG is impossible in the face
> of state compromise, this is not true of other types of random number
> generator.
Um MD5 for RNG. The OP is a newbie and used the wrong term. MD5 cannot be
used to make an RNG at all.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Notion of perfect secrecy
Date: Fri, 08 Jun 2001 10:40:48 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (John Savard) wrote in
> <[EMAIL PROTECTED]>:
>
> >On Thu, 7 Jun 2001 00:39:15 -0700, "Neil Couture"
> ><[EMAIL PROTECTED]> wrote, in part:
> >
> >quoting David A. Scott:
> >>> DUH??? GEE WHIZ length may mean something so pad to make it
> >>> match longest message for "perfect security" READ SHANNON YOU IDOIT
> >>> you can't have it both ways little BOY.
> >
> >>Maybe i read Shannon wrong but as I understand a key of lenght n is
> >>enough for encrypting
> >>a msg of lenght n. that's it.
> >
> >You're both right.
> >
> >If the longest message has length N, but your current message is of
> >length n (and includes an end-of-message indication) you only require
> >a key of length n for perfect secrecy, because the N-n bits remaining
> >may be generated at random by the sender without the intended
> >recipient requiring any additional key bits.
> >
>
> But Tommy only wants to send the number of bits of whatever
> message he choose. He does not wish to mask length of shorter
> messages by sending extra bytes. So though adding random data
> to pad would work. Tommy does not wish to do this.
Tommy wants to keep his job by not wasting resources.
And please dear sir, call me either Tom or St Denis. I don't call you
"Scooter" or "Dunce Man" or ...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:41:33 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
>
> :> [...] if your set is a bunch of different
> :> length messages just XOR and sending then where you always
> :> have more than one possible message for a given length you
> :> may "have some security" but some is not the same as "perfect"
> :> since you have many messages from your input set that have
> :> been iliminated.
>
> : That doesn't matter at all. Even if you know the original message
occupied
> : 128 bits but there are only 13 possible remaining messages it's still
> : perfectly secure. Since the remaining messages have a 1/13 chance of
being
> : the correct one you can't tell the correct one from a false one.
>
> Except for the fact that they are different lengths - so regardless of
> the probability of their arising as plaintexts, you can easily distinguish
> them if given a corresponding cyphertext.
No I was talking about 13 possible messages of 16 chars.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:43:57 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Tim Tyler" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> :> Where the attacker has a priori knowledge that the message is going
> :> to be either "yes" or "no" - but doesn't know which.
>
> : That's just a contrived example of how to not use an OTP. Obviously in
this
> : case the two messages are vastly different.
>
> : If your system calls for sending booleans send bits not ASCII words.
>
> : I mean seriously, outside of a contrived example an OTP is perfectly
secure.
>
> [...]
>
> : Making contrived ways to break something is not only pointless but
futile.
> : It proves nothing.
>
> That single example proves that the OTP is vulnerable to attack
> if plaintext length is equal to cyphertext length, and plaintext lengths
> can vary.
>
> If you don't think it proves anything, you need to re-examine your idea of
> proof.
No, you didn't prove that an OTP can be insecure. You proved that a
cryptosystem using an OTP can be vulnerable.
Just like I said RSA with a 32-bit composite is vulnerable. That doesn't
mean RSA is weak, it means the system is.
Fundamentally an OTP is a decorrelated linear function, from a math point
it's easy to prove it's secure.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:45:08 GMT
"JPeschel" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" [EMAIL PROTECTED] writes:
>
> > >"JPeschel" <[EMAIL PROTECTED]> wrote in message
> > >news:[EMAIL PROTECTED]...
>
> >> Yikes! Now that comparison doesn't make any sense at all. Cipher meant
> >> the same thing then as it does now, for instance, Vigenere cipher,
> >Playfair
> >> Cipher, Vernam cipher, etc.
> >
> >Hmm... perhaps I haven't look at this formally. I always thought cipher
was
> >not a real word.
> >
> >I stand corrected.
>
> Okeedokee. Some would write "okeydokey." I'm not sure if that's a real
word,
> but I like it.
> I think Tim would write okeydoke. :-)
>
> Now isn't that better than all this perfect OTP talk?
>
> What I'd really like is a recipe for a perfect margarita, a recipe with
which
> we can concoct
> at least one perfect pitcher of drinks for one day. I want the recipe to
be a
> true
> margarita. One that screams, "I am a margarita in and of myself." After
one
> perfect
> pitcher of margaritas I won't care if the rest are less than perfect --
until
> the next day
> when it's margarita time again.
Has it been a long day Joe? :-o
tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:47:26 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Tom St Denis wrote:
> >
> > <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Tim Tyler <[EMAIL PROTECTED]> writes:
> > > > [EMAIL PROTECTED] wrote:
> > > >:> The fish are plausible plaintexts. The tank represents files
> > > >:> sorted by size. Files at the end of the tank are shorter than
ones
> > > >:> further away. The directional swimming of the fish represents
> > > >:> compression.
> > > >
> > > >: GLORY, GLORY HALELUJAH! NOW I GET IT! Please, please, write this up
and
> > > >: submit it to the Acta Mathematica...
> > > >
> > > > I assume you didn't understand :-( I figure that makes you a lost
cause.
> > >
> > > Don't go easy on me--give me the full-bore mathematical proof. If you
> > > like, we can trade: I'll send you a copy of my PhD thesis, and you
send
> > > me a copy of your actual proof.
> >
> > What's your thesis on? Mind sending me a copy?
>
> Unless you are a 'collectioner' by nature, I wouldn't
> in your (and my own) place access thesis in math, for these
> are invariably virtually 'undigestable' by non-mathematicians.
> If you already feel very comfortable reading graduate
> textbooks in math (I don't unfortunately), that may not
> apply for you though.
Let you in on a tip. I wouldn't even be this [un]knowledgeable about
comp.sci and crypto (and compiler theory and data compression and automaton
code generators) if I didn't get in over my head.
When I was 14 I took the EMS/XMS memory manuals. At first they were big and
confusing (call this, int that, mov this) however I did eventually write
some support code I needed to use both.
So yeah, I will most likely not understand his thesis. But in time after
re-reading it etc, I might.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Fri, 08 Jun 2001 10:48:04 GMT
"Vincent Quesnoit" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tim Tyler a écrit :
>
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> > : I was referring to the following that you wrote previously:
> >
> > : Yes it is. Consider BICOM for example. It can map a
> > : 8 bit cyphertext to one of some 2^128 plaintexts -
> > : considerably more than your figure of 2^8.
> >
> > : Does the 2^128 come from using a 128 bit key for the
> > : AES in it and there are 2^128 possible keys for AES?
> >
> > Yes.
>
> I am puzzled, I thought AES was a block cypher which could not produce a
> cypher text smaller than its own blocksize. Do you mean that AES can
> decrypt one byte and produce a 16 byte output ?
Yes, in a CTR block mode you can encrypt single bits if you choose.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Simple C crypto
Date: Fri, 08 Jun 2001 10:48:56 GMT
"Dirk Bruere" <[EMAIL PROTECTED]> wrote in message
news:c4YT6.20579$[EMAIL PROTECTED]...
>
> "Tom St Denis" <[EMAIL PROTECTED]> wrote in message
> news:o6XT6.55186$[EMAIL PROTECTED]...
> >
> > > > > That is not a major worry.
> > > >
> > > > Then what is?
> > >
> > > Someone fiddling with a file on a computer because they're bored for
> > 10min?
> >
> > And if they are lucky and happend to know how to make a website?
>
> A copyright lawsuit?
Cough cough. DeCSS.
> > > > Why even bother with crypto? Just xor the file with 0xAA.
> > >
> > > Quite likely a variant of that will be used, unless there is some
> > > almost-as-simple and stronger alternative.
> > > Hence my inquiry.
> >
> > Well if you find something patent it and sell it to the MPAA and RIAA.
> You
> > will make literally millions!
>
> Doesn't sound too difficult.
> Just need a bucket of qubits.
And magic fairy crypto dust.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Simple C crypto
Date: Fri, 08 Jun 2001 10:50:00 GMT
"Samuel Paik" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dirk Bruere wrote:
> > I'm looking for a simple algorithm to code text that is pretty difficult
to
> > break for an amateur without custom s/w.
> > I had thought of something like (say) a 16 bit number, to be XORed with
> > chars, and then this shifted each time it is re-used.
>
> Well, that's awful. If you want a short and simple ciphers yet strong
> ciphers, you might want to check RC4, RC5, RC6, or TEA.
>
> TEA:
> http://vader.brad.ac.uk/tea/tea.shtml
> http://vader.brad.ac.uk/tea/source.shtml#ansi
No offense but I don't count any of those as "strong". RC5 for example I
would only trust with 20 rounds or more. RC6 with 28 or more. RC4 is
showing signs of weakness. TEA is original but not entirely a good design.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Simple C crypto
Date: Fri, 08 Jun 2001 10:50:31 GMT
"Samuel Paik" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dirk Bruere wrote:
> > Let's see now...
> > I've got a time budget of about $50 to spend on this, including coding
and
> > code integration.
>
> $50? That's barely enough time for me to start up Microsoft Developer's
> Studio!
Is that 50$ us? In Canada that would be like a trillion dollars...!
Hey Dirk I want the job!
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and Large
Primes
Date: Fri, 08 Jun 2001 10:52:17 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] (David Wagner) wrote in
> <9fp4cm$2s77$[EMAIL PROTECTED]>:
>
> >Joseph Ashwood wrote:
> >>Take a simpler
> >>problem 1+1=2, everyone learns that in 1st grade (some earlier, some a
> >>little later), but it takes a doctorate in mathematics, and a few
hundred
> >>pages of very intricate math to prove it without assuming things.
> >
> >Bah. One cannot prove 1+1=2 without assuming things.
>
>
> I know it not your style to answer easy questions but
> why don't you go out on a limb and say how one use a
> OTP crypto system. If you have as the possible input
> space several different messages of various length.
> When you encypt using one time pad to get "perfect secrecy"
> in the Shannon sense. If you do and are honest I will
> stop bring up the fact you stated scott19u dead by slide
> attack when in fact you later mentioned you never fully
> understood what my method did.
> Hey I tried.
Not to relive the past over and over.
But David.Scott what formal analysis did you do on your own cipher?
tom
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: RSA's new Factoring Challenges: $200,000 prize.
Date: Fri, 8 Jun 2001 23:00:10 +1200
"Sergei Lewis" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Brown wrote:
> > "Sergei Lewis" <[EMAIL PROTECTED]> wrote
> > > You can set one bit arbitrarily for exactly one of these, since you know
> > > the two factors are different and exactly one bit is set; this on its
> > > own doesn't help resolve all of them.
> > Correct.
> You can't, actually. This assumes equal length factors. If the factors
> are not the same length in bits, the bits you haven't worked out yet
> could be the same in both factors. You have to try the method for every
> combination of factor lengths - there's 2logn of them.
Sorry. I read this wrong. You only should need to (and can) set one of these
boxes to a certain state. If you set more than one you have a chance of setting
it the wrong way around. This is the main sticking point in the whole thing: I
an unable to prove that setting one box is sufficient to complete enough of the
boxes so that the factors can be determined.
> > > Deductions of the form "bit x cannot be set in both factors because of
> > > box y", "bit x must be set in both factors because of box y", and "bit x
> > > must be set in neither factor because of box y" can be used to resolve
> > > these, as Michael's page describes, but you need some really nasty hairy
> > > logic to do this.
> > Dead right. This is where I get stuck too :)
> Quite doable, actually :)
> Don't use 2-input 2-output stages. Use 3-input 2-output stages instead.
<SNIP>
> This method is equivalent to yours, since a three-bit adder can be built
> using several of your two-bit adders.
Is it though? This is like saying that using a 4-input, 4-output adder is
equivilent to mine (which, in a way it is).
However, a 4-input 4-output box cannot be solved in the way that I describe.
This is easily proven by the fact that trial division (ignoring GNFS etc) is the
only way to solve a 2 bit prime * 2 bit prime number. However, this does not
invalidate my method, as it works in this case.
<SNIP>
> This method does not work, since it produces arbitrarily many cases
> where a state has an output carry of 0, an output of 1, and it cannot be
> determined whether this output is from a previous carry, a previous
> output, or the current bit of a. Trying every possible valid combination
> of these states is no faster than trial divison :(:(:(
That's why a 2-input, 2-output box is used :)
Regards,
Michael
------------------------------
From: "Michael Brown" <[EMAIL PROTECTED]>
Subject: Re: Simple C crypto
Date: Fri, 8 Jun 2001 23:05:25 +1200
"Samuel Paik" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Dirk Bruere wrote:
> > Let's see now...
> > I've got a time budget of about $50 to spend on this, including coding and
> > code integration.
>
> $50? That's barely enough time for me to start up Microsoft Developer's
> Studio!
Is that a reflection of Visual Studio or your rates :)
> --
> Samuel S. Paik | [EMAIL PROTECTED]
> 3D and digital media, architecture and implementation
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
