Cryptography-Digest Digest #834, Volume #9 Tue, 6 Jul 99 01:13:03 EDT
Contents:
Re: I need help seeking cryptography-related employment (S.T.L.)
Re: DES-NULL attack (S.T.L.)
Re: Encrypted Boot Sector ("Lyal Collins")
Re: Why this simmetric algorithm is not good? (fungus)
Re: Encrypted Boot Sector (fungus)
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: Help!! Looking for a modular exponentiation algorithm. (Jim Gillogly)
Re: Summary of 2 threads on legal ways of exporting strong crypto (Isaac)
Re: RSA Padding ([EMAIL PROTECTED])
Re: Help!! Looking for a modular exponentiation algorithm. (Bob Silverman)
Re: Solitaire optimization (Johnny Bravo)
Re: Why this simmetric algorithm is not good? (Mr. O. Lanikey)
Re: Why this simmetric algorithm is not good? ([EMAIL PROTECTED])
Re: Summary of 2 threads on legal ways of exporting strong crypto ([EMAIL PROTECTED])
Re: Moores Law (a bit off topic) ([EMAIL PROTECTED])
Re: DES-NULL attack ([EMAIL PROTECTED])
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: I need help seeking cryptography-related employment
Date: 05 Jul 1999 23:56:18 GMT
<<Would someone please respond with a link to the fastest algorithm for
factoring numbers on the order of less than 2^64? The algorithm should
be suitable for programming on a machine with a m68000 processor w/512KB
memory.>>
Let me guess. A TI-92+. I'm right, aren't I? The memory you stated would make
it a TI-92+. Or a TI-89. Their processors run at 10Mhz! Anything you try will
be blazingly slow. :-D
Posted and mailed.
Moo-Cow-ID: 16 Moo-Cow-Message: posts
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^6972593 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
Quantum Mechanics, the Polycarbonate Syndicate, the Roll-Your-Own Crypto
Alliance, and People for the Ethical Treatment of Digital Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
"When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #11: The Strong Force Is Carried By Gluons.
------------------------------
From: [EMAIL PROTECTED] (S.T.L.)
Subject: Re: DES-NULL attack
Date: 06 Jul 1999 00:03:09 GMT
This is a semi-off-topic post. Just be glad I'm not David A. Scott.
<<billion Gigabytes>>
Why not say the real word? People work with gigabytes all the time, so a
billion doesn't seem like that much. However, one Terabyte seems humongous.
Therefore:
1000 gigabytes = Terabyte
Million Gigabytes = Petabyte
Billion Gigabytes = Exabyte
(Readers who are British can kindly keep quiet about the numbering system I'm
using here. Us Americans beat the British in the Revolutionary War, so we have
the right to use whatever darn system we please. Besides, the British can't
spell "color" anyways.)
WOW, an Exabyte! Compare that to the six Exabytes you would need to store every
word ever spoken by a human being. Whoo hoo! An Exabyte sounds _much_ more
impressive than a billion Gigabytes.
Moo-Cow-ID: 50 Moo-Cow-Message: the
-*---*-------
S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^6972593 - 1 is PRIME!
Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
"Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
E-mail block is gone. It will return if I'm bombed again. I don't care, it's
an easy fix. Address is correct as is. The courtesy of giving correct E-mail
addresses makes up for having to delete junk which gets through anyway. Join
the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
.sig is shorter and contains 3379 bits of entropy up to the next line's end:
-*---*-------
Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
Quantum Mechanics, the Polycarbonate Syndicate, the Roll-Your-Own Crypto
Alliance, and People for the Ethical Treatment of Digital Tierran Organisms
Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
"World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
"When Tidal Forces Attack: Caught on Tape"
Patiently awaiting the launch of Gravity Probe B and the discovery of M39
Physics Commandment #11: The Strong Force Is Carried By Gluons.
------------------------------
From: "Lyal Collins" <[EMAIL PROTECTED]>
Subject: Re: Encrypted Boot Sector
Date: Tue, 6 Jul 1999 10:05:47 +1000
Boot sectors have to be read by standard BIOS and bootstrap code.
I'd suggest the Master Boot Record (sector containing the partition table)
also contains some basic assembly code to either read the real boot sector,
or the decode the modified one.
This code will, is disassembled, show how the encoding is done, and if any
key is invovled - the key will most likely be embedded.
Lyal
fungus wrote in message <[EMAIL PROTECTED]>...
>
>
>Zachary wrote:
>>
>> Hi,
>>
>> I have a encrypted boot sector. And then I have the same boot sector
>> but its not encrypted. Is there anyway to find out logarithm that was
>> used to encrypted it. I know that it is in base 64. If that helps
>> you. Are there any programs that can find the logarithm? Any
>> inforamation on decryption would be helpful.
>>
>
>If it was easy to do this then I could find out your secret keys
>quite easily. This would be bad, so encryption systems are designed
>to make this extremely difficult.
>
>
>
>
>
>--
><\___/>
>/ O O \
>\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Why this simmetric algorithm is not good?
Date: Tue, 06 Jul 1999 02:00:23 +0200
[EMAIL PROTECTED] wrote:
>
> Hi,
>
> I'm not a experimented cryptanalyst but there is an encryption algorithm
> (written in a Pascal-like language).
>
> procedure cipher(Key : uint128 ; plain: file ; cipher : file)
> var Kaux: uint128
> begin
> setRandomSeed(Key);
> c = 2^128 - 1
> while not EOF(plain)
> begin
> Kaux := c xor Random(0..2^128-1)
> p := getNext128bits(plain)
> c := p xor Kaux
> writeNext128bits(cipher, c)
> end
> end
>
> What's wrong with this algorithm, besides the Random function strength?
>
Nothing. What you have here is called a steam cipher.
I'm not sure why you're xor'ing the random numbers with the
previous block. It doesn't add any strength to the cipher.
This is just as strong:
procedure cipher(Key : uint128 ; plain: file ; cipher : file)
begin
setRandomSeed(Key);
while not EOF(plain)
begin
p := getNext128bits(plain) xor Random(0..2^128-1)
writeNext128bits(cipher, p)
end
end
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Encrypted Boot Sector
Date: Tue, 06 Jul 1999 01:55:54 +0200
Zachary wrote:
>
> Hi,
>
> I have a encrypted boot sector. And then I have the same boot sector
> but its not encrypted. Is there anyway to find out logarithm that was
> used to encrypted it. I know that it is in base 64. If that helps
> you. Are there any programs that can find the logarithm? Any
> inforamation on decryption would be helpful.
>
If it was easy to do this then I could find out your secret keys
quite easily. This would be bad, so encryption systems are designed
to make this extremely difficult.
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Mon, 05 Jul 1999 23:36:13 GMT
In article <7lq5jc$hrm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> First off. ***THE PLAINTEXT AND CIPHERTEXT ARE THE SAME SIZE*** You
> have padding on the plaintext for short messages so that they are
> always the same length.
Well, I have no objection at all to the above. I had quite a long look
at RSA to know it is true. As I suggested in my original, we can no
longer call the algorithm I have written down (if it works, that is)
RSA. It is something that can be used to have lm+1 bits of message
length, and l_N-l_m-1 bits of equivalent RSA strength (if there is no
weakness introduced by my musings). l_N is the bit length of the
modulus. You see, even in what I am suggesting the message length and
the cyphertext length are equal. The only difference I am suggesting is
that this length is NOT EQUAL to the modulus length.
> Second no v exist where v != pq which will decrypt a message. This is
> because what if v is smaller? Then you have pq - v messages that
will
> not decrypt (they will have two solutions). Same if v > pq...
Well, you don't seem to get the gist of the original problem, and the
solution I am suggesting. Let me describe it a bit more clearly:
1. message length and cyphertext length are l_m+1 bits (well, not
exactly true, message length should be l_m bits)
2. modulus length is l_N bits, which is about an order of magnitude
larger compared to l_m (which has no significance at all, you can make
the difference smaller, but the it will not be what Gilad has asked).
3. It is obvious that if you try to encrypt messages larger than v, you
cannot get the original message back, because of the final modulus
operation. In that sense, you are right. But since we only require l_m
bits in the message, having floor(log2(v))==l_m+1 guarantees that all
messages we want to encrypt are less than v.
4. There is such a v. When you expand (k_c*v+c')^d mod N, you wil get a
polynomial in v, which is
(a_0*v^d + a_1*v^d-1 + .... + a_(d-1)*v + a_d) mod N, a_d = c'^d
If you can find a v, for which [(v^i mod N) mod v ]== 0 for all i, then
you can use that v to achieve the solution to Gilad's problem. This is
because
M < v, M == (k_c*v+c')^d mod N
=> M mod v == ((k_c*v+c')^d mod N) mod v
=> M == a_0*v^d + ... + a_d mod N
=> M == (a_d mod N) mod v == c'^d mod N mod v
We can write the last step, because all terms of the polynomial, except
the last one, evaluated mod N will be a multiple of v, and wil be equal
to zero mod v. I need to have a more careful look at it to say that it
is guaranteed to be so.
Unfortunately, the only such v are p, and q (and perhaps p^i for all i
which make p^i<N, which I failed to mention in my original post,
because I am still not sure about it) when N=p*q.
You don't want to give away one of your factors in N, therefore I
suggested the second algorithm where N=p*q*r, and you give away r.
Any specific objections to what I have described above? It is not RSA,
but it should still require random padding, because it uses the
underlying theory of RSA, therefore, I expect it to be vulnerable to
whatever RSA is vulnerable to. But if I am not mistaken, it gives you
smaller block length, without reducing the strength obtained by modulus
length too much. If you ask "Is this a good thing?", I would say "I
don't know, but I know better than using a home brewed algorithm in any
serious application.". Anyway, I found the solution while pondering on
Gilad's question, and wanted to share it with people here. Perhaps
someone somewhere can find a good application for the algorithm, and
examine it further.
If there is any part you did not understand (I am not a good teacher, I
know), and want to have more information on, just ask.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Help!! Looking for a modular exponentiation algorithm.
Date: Mon, 05 Jul 1999 19:03:25 -0700
Keith Reeves wrote:
> I'd really appreciate if someone could help me out! I'm looking for a
> modular exponentiation algorithm, one that can be used with RSA. Could
> anyone point me in the right direction? If anyone knows where I can
> find one of these on the web, explained in semi-layman terms, it would
> be a big help.
The bignum library that comes with SSLeay has what you're looking for.
If you'd rather roll your own, try "Handbook of Applied Cryptography",
by Menezes et al., and plan on spending a little programming time on
it if you need it to be fast. Some background from Knuth vol. II
(Seminumerical Algorithms) will also be helpful.
--
Jim Gillogly
Highday, 13 Afterlithe S.R. 1999, 02:00
12.19.6.6.1, 12 Imix 9 Tzec, Fourth Lord of Night
------------------------------
From: [EMAIL PROTECTED] (Isaac)
Crossposted-To: talk.politics.crypto
Subject: Re: Summary of 2 threads on legal ways of exporting strong crypto
Date: 5 Jul 1999 21:52:37 GMT
On Mon, 05 Jul 1999 18:55:56 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>Boris Kazak's method is NOT a steganographic technique. It is an
>'open' encoding of bits into the English text. Anyone, from justice
>department or not, can recover the information. The point is that
>English texts are exportable. There is nothing forbidding one's
>writing English texts using lower case or upper case. (Would one
>be punished if one e.g. occasionally misspells a word in his e-amil?)
>
English text on paper is exportable. No 'open' encoding required.
This means print outs of source code can be hand carried or mailed
overseas while electronic transmission of the exact same material
without an export license is illegal.
What you hope to accomplish in your transform appears to be
hiding illegal activity rather than accomplishing a legal
transaction. I find speculation on whether you'll get caught
uninteresting.
I sincerely hope no one follows any advice from your 'summary'. It
doesn't appear to reflect anything I've seen posted in this newsgroup.
Isaac
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA Padding
Date: Tue, 06 Jul 1999 02:17:50 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (S.T.L.) wrote:
> <<Encrypt a message with RSA in byte size blocks and I will crack your
> message in under a day...>>
>
> Who'd do such a thing? When I encrypt with RSA (on my TI-92) and
don't use
> padding, I break my message up into chunks that are the size of the
modulus,
> which can be, say, 800 bits. That can't be frequency analyzed.
Well you said having 3-digit msgs... that's why I said freq analysis
would work.
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Help!! Looking for a modular exponentiation algorithm.
Date: Tue, 06 Jul 1999 02:03:09 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Keith Reeves) wrote:
> I'd really appreciate if someone could help me out! I'm looking for a
> modular exponentiation algorithm, one that can be used with RSA. Could
> anyone point me in the right direction? If anyone knows where I can
> find one of these on the web, explained in semi-layman terms, it would
> be a big help.
>
Here is a simple method: (basic binary algorithm)
To compute b^k mod N
(1) represent k in binary.
(2) delete the most significant 1 in k. Let the length of k in binary be r
(3) Set x = b
(4) for i = r-1 to 0 step -1
{
x <-- x^2,
if the ith bit is 1 then x = x*b
reduce x mod N
}
return(x)
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: Solitaire optimization
Date: Mon, 05 Jul 1999 21:54:46 GMT
On Sun, 04 Jul 1999 19:46:53 +0200, fungus
<[EMAIL PROTECTED]> wrote:
>This would be ok if mistakes didn't accumulate. A couple of bad letters
>in a message wouldm't make it unreafable.
It depends on what the mistake was. If you make a mistake with a
letter value or write down the wrong result you lose one letter, if
you make a mistake with the deck you lose the rest of the message.
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Mr. O. Lanikey)
Subject: Re: Why this simmetric algorithm is not good?
Date: Tue, 06 Jul 1999 03:17:20 GMT
fungus <[EMAIL PROTECTED]> wrote:
>Nothing. What you have here is called a steam cipher.
I suggest replacing it with a more modern diesel cipher.
------------------------------
Date: Mon, 05 Jul 1999 12:21:20 -0400
From: [EMAIL PROTECTED]
Subject: Re: Why this simmetric algorithm is not good?
Francois Grieu wrote:
>
> [EMAIL PROTECTED] wrote :
> > (128 bits stream cipher deleted)
> >
> > What's wrong with this algorithm, besides the Random function strength?
>
> 0) The algorithm is probably weak unless the Random function is designed
> for crypto
>
> 1) someone actively intercepting a ciphertext can flip whatever bit of
> plaintext
>
> 2) someone managing to get a ciphertext and it's corresponding plaintext
> can decipher or forge messages using the same key, of length up to
> the intercepted message size
Actually it is much worse than this. Someone with a
plaintext/ciphertext pair will be able recover an equivalent length
subset of the keystream. With only a few blocks of the keystream all
subsequent key values can be predicted, so all successor messages are
trivially broken until there is an out-of-band reset of the key stream
seed.
>
> 3) someone intercepting several ciphertext enciphered with the same key
> can detect that some bits are indentical to previous messages at a
> given position; can be usefull if the purprose is to detect something
> unusual (e.g. the message starts in "ALERT !!!" instead of "dear sir")
>
> 4) there is no provision for messages not a multiple of 128 bits
>
> Francois Grieu
------------------------------
Date: Mon, 05 Jul 1999 12:17:31 -0400
From: [EMAIL PROTECTED]
Crossposted-To: talk.politics.crypto
Subject: Re: Summary of 2 threads on legal ways of exporting strong crypto
Mok-Kong Shen wrote:
>
> [EMAIL PROTECTED] wrote:
> >
>
> >
> > How is this steganographic technique better than applying ROT-13 to the
> > source code?
> > If a justice department investigator can apply a simple transform to the
> > message and produce a working program capable of strong crypto, he will
> > conclude tha the laws have been broken.
>
> Boris Kazak's method is NOT a steganographic technique. It is an
> 'open' encoding of bits into the English text. Anyone, from justice
> department or not, can recover the information. The point is that
> English texts are exportable. There is nothing forbidding one's
> writing English texts using lower case or upper case. (Would one
> be punished if one e.g. occasionally misspells a word in his e-amil?)
I believe you have missed my point. Of course it is English text, and
there are no laws against exporting English text. But it is _also_ a
machine-readable form of strong crypto source code, and there are laws
against exporting such.
If there were laws against exporting English text, and no laws against
exporting machine-readable souce code for strong crypto would you still
maintain it was exportable because one form of interpretation was not
prohibited?
------------------------------
Date: Mon, 05 Jul 1999 12:26:49 -0400
From: [EMAIL PROTECTED]
Subject: Re: Moores Law (a bit off topic)
fungus wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> >
> > Really well I will teleport us 200 years into the future. RSA-128 bit
> > challenges are on the block. I have my 250Ghz program running 2^64 keys
> > a second... blah blah blah. Now how strong is a 256 bit key? It will
> > only be another 100 years before it falls.
>
> 250GHz?
>
> Let's see now.
>
> At 250 GHz an electron could only travel about a millimeter, max.
> Your entore CPU and memory will have to fit inside something a
> millimeter in diameter.
>
> 250Ghz is about 2^37Hz. If you can check one key per clock cycle
> (where go you get your figure of 2^64 from???)
It's a 128 Meg system. Not bytes, CPUs.
then you've still
> got 219 bits of key to crack....you're not going to see a result
> before the sun burns out.
>
> --
> <\___/>
> / O O \
> \_____/ FTB.
------------------------------
Date: Mon, 05 Jul 1999 12:30:20 -0400
From: [EMAIL PROTECTED]
Subject: Re: DES-NULL attack
S.T.L. wrote:
>
> This is a semi-off-topic post. Just be glad I'm not David A. Scott.
>
> <<billion Gigabytes>>
>
> Why not say the real word? People work with gigabytes all the time, so a
> billion doesn't seem like that much. However, one Terabyte seems humongous.
> Therefore:
> 1000 gigabytes = Terabyte
> Million Gigabytes = Petabyte
> Billion Gigabytes = Exabyte
> (Readers who are British can kindly keep quiet about the numbering system I'm
> using here. Us Americans beat the British in the Revolutionary War, so we have
> the right to use whatever darn system we please. Besides, the British can't
> spell "color" anyways.)
Formally, you are supposed to quote Churchill here!
>
> WOW, an Exabyte! Compare that to the six Exabytes you would need to store every
> word ever spoken by a human being. Whoo hoo! An Exabyte sounds _much_ more
> impressive than a billion Gigabytes.
>
> Moo-Cow-ID: 50 Moo-Cow-Message: the
>
> -*---*-------
> S.T.L. ===> [EMAIL PROTECTED] <=== BLOCK RELEASED! 2^6972593 - 1 is PRIME!
> Quotations: http://quote.cjb.net Main website: http://137.tsx.org MOO!
> "Xihribz! Peymwsiz xihribz! Qssetv cse bqy qiftrz!" e^(i*Pi)+1=0 F00FC7C8
> E-mail block is gone. It will return if I'm bombed again. I don't care, it's
> an easy fix. Address is correct as is. The courtesy of giving correct E-mail
> addresses makes up for having to delete junk which gets through anyway. Join
> the Great Internet Mersenne Prime Search at http://entropia.com/ips/ Now my
> .sig is shorter and contains 3379 bits of entropy up to the next line's end:
> -*---*-------
>
> Card-holding member of the Dark Legion of Cantorians, the Holy Order of the
> Catenary, the Great SRian Conspiracy, the Triple-Sigma Club, the Union of
> Quantum Mechanics, the Polycarbonate Syndicate, the Roll-Your-Own Crypto
> Alliance, and People for the Ethical Treatment of Digital Tierran Organisms
> Avid watcher of "World's Most Terrifying Causality Violations", "When Kaons
> Decay: World's Most Amazing CP Symmetry Breaking Caught On [Magnetic] Tape",
> "World's Scariest Warp Accidents", "World's Most Energetic Cosmic Rays", and
> "When Tidal Forces Attack: Caught on Tape"
> Patiently awaiting the launch of Gravity Probe B and the discovery of M39
> Physics Commandment #11: The Strong Force Is Carried By Gluons.
------------------------------
** 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
******************************
