Cryptography-Digest Digest #505, Volume #9 Wed, 5 May 99 23:13:03 EDT
Contents:
Re: Shamir's TWINKLE Factoring Machine ([EMAIL PROTECTED])
partition id of scramdisk ("Maggus")
Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO (SCOTT19U.ZIP_GUY)
Re: Shamir's TWINKLE Factoring Machine (ca314159)
Re: Discrete Logarithm Question ("Vedat Hallac")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Jerry Coffin)
Re: Fast random number generator (Herman Rubin)
Roulettes (Mok-Kong Shen)
Re: Shamir's TWINKLE Factoring Machine (Bruce Schneier)
Re: Shamir's TWINKLE Factoring Machine (David A Molnar)
DECT/GAP cordless phone encryption algorithm ("Rene Laederach")
Re: Some thoughts on Diffusion ("Malcolm Herring")
Re: Shamir's TWINKLE Factoring Machine (DJohn37050)
Re: Embarrassing question about Blowfish ([EMAIL PROTECTED])
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
([EMAIL PROTECTED])
Re: Arab Terrorists Must Bomb Moscow & Belgrade KKKommunists (Vladimir Beker)
Re: Roulettes (Boris Kazak)
The simplest to understand and as secure as it gets. (Anthony Stephen Szopa)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: Wed, 05 May 1999 21:43:45 GMT
<snip>
Thanks for the info, btw where could someone (maybe I :) ) find info on the
details of factoring a RSA number or a Discrete log?
I would just to like to know the technique and not nesscesarily all the
steps..
Is this covered in AC? (I will check later ...)
Tom
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Maggus" <[EMAIL PROTECTED]>
Subject: partition id of scramdisk
Date: Wed, 5 May 1999 23:59:31 +0200
Hello
I scrambled a whole partition with scramdisk. Unfortunately I deleted this
partition with fdisk. I have the possibility to get it back if I know the
partition id of scramdisk.
Can anyone help me?
Thanks very much
Marcus
------------------------------
From: SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]>
Subject: Re: BEST ADAPTIVE HUFFMAN COMPRESSION FOR CRYPTO
Date: Wed, 05 May 1999 23:05:34 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > Do you really want me to find the reference. And would it shut you
> > up or just piss you off more?
>
> Do you think that I am joking????? Let's see who is the liar!!
Well I figured you are either joking or have a very bad memory
as you said your English is not very good.
...snip..
> >
> > Well if you bothered to look at my code or examples then you can
> > see what the method does. But your mind up to this point is to closed
> > and to lazy to look. The point is you don't have to put all zeros
> > or ones in. It just seems that most people who code sompression routines
> > never give much thought about how to end the file in a nice way.
>
> I wrote (or didn't real my post carefully??) that, among others
> it is illegal for me to fetch crypto-code from US. Any if you have
> any good method, it is certainly possible to express that in
I have read your posts though I can't figure out why. You can never
seem capable of simple reasoning. Since I guess I must state AGAIN
that the COMPRESSION CODE is not ENCRYPTION why you can't see that
is beyond me. Yes the compression code with examples sources and
an executable is at me site. But if you could read and was able to
retain this fact you would already know that since THIS WAS EXPLAINED
very carefully to you before.
But I realize that even after reading this again you still will
not understand what I have said. So I will no longer anwser posts
in this thread with you until you make some sense. So good bye.
David Scott
P.S. Pascal sucks big time to C. No wonder you are having
trouble with simple C code.
--
http://cryptography.org/cgi-bin/crypto.cgi/Misc/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
to email me use address on WEB PAGE
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: Wed, 05 May 1999 23:04:01 GMT
Bruce Schneier wrote:
>
> At Eurocrypt this week, Adi Shamir presented a new machine that could
> increase our factoring speed by about 100-1000 times. Called TWINKLE
> (The Weizmann INstitute Key Locating Engine), this device brings
> 512-bit keys within the realm of our ability to factor.
Twinkle:
http://www.jya.com
___
http://www.bestweb.net/~ca314159/
dejanews problems
------------------------------
From: "Vedat Hallac" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm Question
Date: Thu, 6 May 1999 09:54:31 +1000
Thanks for the quick reply. I found your answers most enlightnening. However
I have a few questions.
>In order to solve the discrete logarithm mod N, the only solution is to
>factor N,
>to solve the problem modulo each factor p_i, and finally to glue the
partial
>solutions
>modulo Phi(p_i)=p_i-1, using the chinese remainder theorem .
This must be some sort of universal joke. The problem came up when I was
trying to find a different approach to factorization. All worthy methods
seem to use the non trivial square root of 1 to solve factorization problem,
and I thought perhaps there might be some properties overlooked by thousands
of people. Not likely? You can never get too lucky.
>3) The fact that the only solution is to factor N, is easily proven. The
>proof follows:
>Assume that you find an algorithm which for any y, g modulo N outputs x
such
>that g^x=y (mod N). Then you can factor N. To do it, choose a large random
>number r (eg N<r<2N), compute y=g^r, and ask for the log. of y say x. Then
>D=r-x is a multiple of Phi(N). Write D as 2^t O where
>O is odd. The final phase is to choose random values Z mod N, to compute
>W=Z^O, and to repeatedly square W. With a little luck, you find an non
>trivial square root of 1 and thus a factor
>of N.
Hmmm.... I can see why finding x solves factorization. But what is missing
in the proof is why factorization has to be the only way to find x. I
understand that if there was a way, factorization problem would have been
solved by now, but the proof as you have stated does not say that there is
no other way of doing it. Or does it?
Also I cannot see why you need to write D as 2^t*O. If D is a multiple of
Phi(N), then it would be sufficient to write D as 2*O (should I assume N is
odd? Of course), and try a single squaring. I bet you would get a
non-trivial square root of one with equal chance with the method you
suggested. If you choose a t > 1, you can find another square root of one
before you square W t times, but it does not seem too important.
The problem came up from something along the lines of the proof you have
posted (a more primitive version, you might say). If N = p*q, with p and q
prime, and Phi(N) > p+q,
then for any 0<a<N,
a^(N+1) == a^(p+q) ( mod N )
If Phi(N) < p+q, you can use the fact that N+1-x is a multiple of Phi(N). So
you see why I asked the question. It seems pretty strange that you know all
a_i, b_i pairs available, and still cannot find any x.
Of course you can do a simple search to find (p+q) with a=2:
k=2^(N+1) mod N;
p_plus_q = 0;
while(k!=1) {
if( Odd(k) ) {
k = k + N;
}
k = k / 2;
p_plus_q = p_plus_q + 1;
}
This function will eventually terminate... But the keyword is not terminate.
It is eventually. :-)
There are more optimized versions of this search, but the best I could come
up with can increment p_plus_q as much as the number of bits in N in one
iteration.
Anyone have any comments?
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Wed, 5 May 1999 16:48:40 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> The process starts off with agreement on keys and cipher in the normal
> way: either transported as a secure secret, or under a certified
> public key.
If it/they are transported under a public key, then the number of
other forms of encryption may be moot -- if the public key encryption
is broken, the key(s) can be recovered, and the attacker can decrypt
the rest of the message without breaking any other forms of
encryption. You'd have a situation similar to that of PGP at the
present time: the security of the system overall is no better than
that of the system used to encrypt the key. You might (as PGP does)
get improvements in speed over using PK cryptography on the entire
message, but you wouldn't get any real improvement in the system's
security.
> Instead of a cipher name, the cipher itself could be
> sent, as C, binary, or whatever.
This seems to be to form a problem of its own -- sending such a
message from within the USA to outside the USA would involve exporting
the encryption (or at least the decryption) code, for which one would
apparently have to obtain a license, at least if (s)he wanted to send
such messages legally. Given the likelihood of all users obtaining
such licenses, (essentially nonexistent) it's fair to say that almost
anybody in the US who used such a system would become a criminal.
------------------------------
From: [EMAIL PROTECTED] (Herman Rubin)
Subject: Re: Fast random number generator
Date: 5 May 1999 20:07:45 -0500
In article <[EMAIL PROTECTED]>,
John Savard <[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote, in part:
>>>The classical shuffling algorithm depends on a good random number
>>generator to produce small random numbers in the range [0, size-1].
>No, it needs more than that.
>It needs one random number in the range {0, 1, 2, ... size-1 }, and
>then it needs one random number in the range {0, 1, 2, ... size-2 },
>and then one in the range {0, 1, 2, ... size-3 }.
>Usually, the classical shuffling algorithm is implemented using a
>generator of random numbers in the range [0,1), which cnn then be
>converted easily to random integers from any range desired.
>My algorithm, though, only requires random bytes, and doesn't need to
>do multiplication or division to convert them to other ranges.
Assuming that one is going to get the above random integers one at
a time, the most bit-efficient method. as far as random bit usage
goes, is simple and essentially unique.
--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Dept. of Statistics, Purdue Univ., West Lafayette IN47907-1399
[EMAIL PROTECTED] Phone: (765)494-6054 FAX: (765)494-0558
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Roulettes
Date: Wed, 05 May 1999 17:46:49 +0200
The German lottery provides at the kiosks little roulettes with balls
in them to ease the customers' task of choosing the numbers on the
lottery tickets. Wouldn't similar devices be good for choosing keys
for encryption?
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Bruce Schneier)
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: Thu, 06 May 1999 01:21:17 GMT
On 5 May 1999 22:18:42 GMT, [EMAIL PROTECTED] wrote:
>[EMAIL PROTECTED] (Bruce Schneier) writes:
>>The important thing to note is that this new machine does not affect
>>the matrix step at all. And this step explodes in complexity for
>>large factoring problems; its complexity grows much faster than the
>>complexity of the sieving step. And it's not just the time, it's the
>>memory requirements. With a 1024-bit number, for example, the matrix
>>step requires something like ten terrabytes of memory: not off-line
>>storage, but real computer memory. No one has a clue how to solve
>>that kind of problem.
>
>Uh, give it time.
>
>Right now I admin some 8 gig RAM machines. It's been maybe 15
>years since 8 meg machines were this expensive (okay, I was 14 in
>1985, sue me if i'm off by a few years). So presumably in 10-15
>years we'll have 8 terabytes of RAM.
Indeed.
>And I'm sure the NSA could build a machine with 8 terabytes of RAM
>right now. Certainly within a few years. And would it be theoretically
>possible to tune the algorithm so that it could be cache- and swap-friendly?
This I don't know. It is certainly concievable, but at first glance
it seems impossible.
>>This technique works just as well for discrete-logarithm public-key
>>algorithms (Diffie-Hellman, ElGamal, DSA, etc.) as it does for RSA.
>>(Although it is worth noting that the matrix problem is harder for
>>discrete-log problems than it is for factoring.) The technique does
>>not apply to elliptic-curve-based algorithms, as we don't know how to
>>use the sieving-based algorithms to solve elliptic-curve problems.
>
>Could there be mathematical advances which make the matrix problem for
>the discrete-log problem equivalent to the factoring one?
I don't think so. For RSA, you can solve the linear equations in mod
2. For discrete log systems, you have to work modulo the
chracteristic of the field.
>Does the NSA
>know how to apply this technique to elliptic curve systems?
You'll have to ask them. Although there are rumors that the NSA is
using discrete log systems, which implies not. But they are only
rumors.
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
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: 6 May 1999 01:13:06 GMT
[EMAIL PROTECTED] wrote:
> right now. Certainly within a few years. And would it be theoretically
> possible to tune the algorithm so that it could be cache- and swap-friendly?
This is what bothers me most in terms of an entity like the NSA - they have the
time and people to investigate practical issues in implementing these algorithms.
These are optimizations which I haven't seen covered much in papers themselves
(maybe in block cipher land?) -- indeed, an article passed out in class last
week flat out admitted that no one in the public world had a large amount of
experience with implementing these things. The article was from the late '80s, so
perhaps things are a bit different now (wasn't there a large effort just
recently?), but it points to a problem.
OK, I found it : p.16 of "The Discrete Logarithm Problem" by Kevin S. McCurley. There's
no date on the paper, but the challenge in it matches the 1989 challenge on his
web page (which has been solved. darn. oh well, there's lots more. lattices anyone?)
BTW, this paper is a very readable introduction to the subject of discrete log
algorithms. I can't find it on his web site (http://www.swcp.com/~mccurley/index.html)
but maybe e-mail would help.
> Could there be mathematical advances which make the matrix problem for
> the discrete-log problem equivalent to the factoring one?
Where exactly does the "more difficult" lie? does it have to do with
the fact that discrete log algorithms require so much more space?
I want to say that the difference between the two is that we have a notion
of "smoothness" for primes, but no corresponding notion for discrete logs,
and therefore end up having to build a much larger table of discrete logs
than possible L(something)-smooth primes. Unfortunately I think I need to
go sit down and look at the algorithms again to pin that down.
>Does the NSA
> know how to apply this technique to elliptic curve systems?
Dunno. If I did I probably couldn't tell you. :-)
-David
------------------------------
From: "Rene Laederach" <[EMAIL PROTECTED]>
Date: Thu, 06 May 1999 02:21:39 +0100
Subject: DECT/GAP cordless phone encryption algorithm
Hi!
Does anybody have a good link or information about the
encryption algorithm used in DECT/GAP cordless telephones
(like the Siemens Gigaset series) or is this one more of
these 'security through obscurity' schemes?
(AFAIR, DECT/GAP is only used in Europe).
--
FIDO: 2:301/133 & 135 | Member We're returning!
Internet [EMAIL PROTECTED] | Team AMIGA - the true avantgarde
------------------------------
From: "Malcolm Herring" <[EMAIL PROTECTED]>
Subject: Re: Some thoughts on Diffusion
Date: Wed, 5 May 1999 18:32:03 -0700
> Robert Scott wrote:
> >
> > While experimenting with different Feistel-like symmetric
> > ciphers, I had some thoughts on ways of quantifying diffusion.
> >
> > While the overall security of a cipher can never be known
> > for certain until it is broken, diffusion has been at least
> > a good indicator of probable security. By diffusion I mean the
> > action of an input data bit having an effect on a large
> > part (hopefully all) of the output block. When applied to ciphers
> > with rounds, I mean diffusion to apply specifically to the rate
> > at which the effect of an input bit spreads as a function of
> > rounds.
...
Surely diffusion says nothing at all about the security of an algorithm. One
can propose any number of keyless scrambling systems (LFSRs, for example)
which have very high diffusions of input data but which are otherwise
equivalent to plain text.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Shamir's TWINKLE Factoring Machine
Date: 6 May 1999 01:55:25 GMT
The NSA representatives at ANSI X9F1 and at IEEE P1363 (these have been a few
different people) have consistently said that they like elliptic curve crypto.
Also, remember that the DSA was designed by NSA.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Embarrassing question about Blowfish
Date: Thu, 06 May 1999 01:51:52 GMT
[EMAIL PROTECTED] wrote:
> I'm planning to implement Blowfish, specifically cfb64 mode from Eric Young's
> code.
>
> I'm having problems understanding the use of the initialisation vector.
>
> Suppose I've loaded the IV with 8 bytes from a unique sequence, and called the
> encrypt routine. What 's my 'cyphertext'? Particularly if the plaintext is
> short (5 or 6 chars, say)?
XOR the first bytes of the encrypted IV with the plaintext
to get the ciphertext.
[...]
> Similarly, on decryption, do I need to slice the first (8? variable?) bytes
> from the cyphertext and make them the IV?
That depends on whether you sent the IV as the first block of
ciphertext. Most crypto protocols have threat the IV is a
distinct data element, so if you encrypt a 5 bytes message
under CFB, you'd transmit an 8-byte IV and a 5-byte ciphertext.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Thu, 06 May 1999 01:30:33 GMT
John Savard wrote:
> Earlier in this dialogue, I felt that Bryan Olson had a legitimate
> objection to your scheme as he understood it, but that he may have
> misunderstood your concept, or you had anticipated that problem, and
> included precautions against it.
That's always a risk, though I try never to misrepresent anyone's
position. Terry Ritter had posted quite a spectrum of ideas, but
the only motivation I could see for a pool of 1000 ciphers is the
dynamic choice among them.
> On the one hand, I see that I was somewhat mistaken, since you are
> defending this point. But your defence does raise a valid point that I
> missed. I don't wish to offend either party to this debate, but I fear
> that I may risk doing so to both, as I am about to put words into both
> of your mouths in order to show how I currently understand your views.
>
> First, I believe Bryan Olson views the question of designing a strong
> cipher in this way:
>
> - Due to the strength and sophistication of such attacks as
> differential and linear cryptanalysis, it is difficult for a layperson
> to design a cipher which will resist these attacks, and
>
> - someone with the required background could spot the weakness in such
> a cipher with relatively minimal time and effort,
>
> - and if we insist on using 1000 different ciphers, some of them will
> be designed by laypersons.
Well certainly I can't take offense.
I do believe that amateurs can design strong symmetric ciphers,
provided they know some fundamentals, work carefully, and build
in large safety factors.
To me, a strong cipher is one for which there is no tractable
break. If a devastating attack exists, the difficulty of finding
it does not, in my view, have anything to do with the strength of
the cipher.
> If this picture of the situation is true, it would seem to be a
> telling argument against your proposed design.
>
> But I don't quite agree with that picture myself. I agree that a
> straightforward DES-like block cipher, with its regular structure, is
> a tricky thing to design. But I've attempted to illustrate, with some
> elaborate designs, such as Quadibloc III, how one could, by being
> willing to introduce extra complications into a cipher design, bring
> designing a secure cipher "down to earth". You have a number of cipher
> designs based on novel principles, and they haven't been shown to be
> weak either, and they can be used as the basis for families of
> ciphers.
>
> And so I think that the condition you are identifying can be met:
> where each cipher, out of a pool of 1000 or so, would require a
> _non-trivial_ amount of effort and resources to defeat. Once that
> condition is met, however, using *one* of those 1000 ciphers at random
> for each message still allows an attacker to concentrate his efforts
> on one of those 1000 ciphers to read a few of your messages.
>
> This would still be an improvement over the situation of using just
> one cipher, since the "just one cipher" would be openly attacked by
> academics and by a multitude of attackers, if we could be sure that
> none of those 1000 ciphers was significantly weaker than the "just one
> cipher" in a way that was relatively easy to spot.
How would you go about breaking any of 1000 given ciphers?
Would you choose a cipher and work only on that one until you
found a fully practical break or died? I'd try to approximate
a "best first search". I'd start work on a cipher by trying
to distinguish the permutations induced by the keyspace from
random permutations, perhaps using weakened variants. I'd take
the ciphers for which I succeeded and try progressively more
practical attacks on variants that were closer and closer to
the full versions. I don't think hiding a weak cipher among
a thousand strong ones buys much.
[...]
> And so this all boils down to how likely a cipher is to be bad, in a
> way that is easily detectable. The difficulty of cracking the cipher
> used to communicate which ciphers are being used is something I
> haven't touched on, and that will certainly contribute to the strength
> of the system.
And not in the way people seem to think. Ciphers by themselves
offer poor authentication, and the authentication of the selection
channel is far more important than its privacy. If I can find a
way to forge, I can get you to use _my_ choice of your ciphers.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
Date: Wed, 05 May 1999 10:51:57 +0300
From: Vladimir Beker <[EMAIL PROTECTED]>
Crossposted-To: sci.med.transcription,sci.space.policy,sci.electronics.repair
Subject: Re: Arab Terrorists Must Bomb Moscow & Belgrade KKKommunists
Come on!!!
People who use cryptographic newsgroup to propose bombing don't have to
know the difference
Vladimir
Lewis Sellers wrote:
>
> [EMAIL PROTECTED] wrote in message
> <7f0i68$s4m$[EMAIL PROTECTED]>...
> >Why aren't the wimpy Syrian, Iraqi, Libyan, Afghani, etc., pussy terrorist
> >dogs bombing Moscow and Belgrade???!!! Where are the oil-rich,
> >Rolls-Royce-riding Arab Muslims from Kuwait, Saudi Arabia after American
> and
> >other NATO soldiers died saving their greedy asses???!!!
> >
> >It's obvious that the KKKommunist-Nazis in Russia and Serbia are the real
> >Great Satans killing, raping, and pillaging Albanian Muslims, but where is
> >the shock and outrage from the Arab Muslims???!!!
>
> Actually the serb leaders are Marxists, not Communists.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Roulettes
Date: Wed, 05 May 1999 19:43:42 -0400
Reply-To: [EMAIL PROTECTED]
Mok-Kong Shen wrote:
>
> The German lottery provides at the kiosks little roulettes with balls
> in them to ease the customers' task of choosing the numbers on the
> lottery tickets. Wouldn't similar devices be good for choosing keys
> for encryption?
>
> M. K. Shen
=====================
Just use octahedric dice (8faces) and get your random numbers in octal.
Best wishes BNK
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.privacy
Subject: The simplest to understand and as secure as it gets.
Date: Wed, 05 May 1999 20:00:12 -0700
Reply-To: [EMAIL PROTECTED]
The simplest encryption software, the easiest to understand, and as
secure as it gets.
Original Absolute Privacy - Level3 Version 4.0 Windows GUI - SHAREWARE
http://www.ciphile.com
------------------------------
** 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
******************************
