Cryptography-Digest Digest #958, Volume #13 Wed, 21 Mar 01 07:13:01 EST
Contents:
Re: Strong Primes (Peter Engehausen)
Re: A future supercomputer (Frank Gerlach)
Re: Defining a cryptosystem as "broken" (Mok-Kong Shen)
Re: Codes that use *numbers* for keys (Daniel)
Re: A future supercomputer (Mok-Kong Shen)
Re: looking for "Crowds" (Mok-Kong Shen)
Re: NSA in the news on CNN ("Mxsmanic")
Re: NSA in the news on CNN ("Mxsmanic")
Re: Is Evidence Eliminator at all useful ?? (David Schwartz)
What happens when RSA keys don't use primes? ("Mxsmanic")
Re: What happens when RSA keys don't use primes? (Mok-Kong Shen)
Re: What happens when RSA keys don't use primes? ("Mxsmanic")
Re: I encourage people to boycott and ban all Russian goods and services, if the
Russian Federation is banning Jehovah's Witnesses ....... ("????")
Hours of work done on RSA, ECC or NTRU ? (Jyrki Lahtonen)
Re: How to eliminate redondancy? (moving steadily towards being computer science
terminology) (those who know me have no need of my name)
Re: => TV detection (was: FBI easily cracks encryption ...?) (Richard Herring)
Re: What happens when RSA keys don't use primes? (Hard)
----------------------------------------------------------------------------
From: Peter Engehausen <[EMAIL PROTECTED]>
Subject: Re: Strong Primes
Date: Wed, 21 Mar 2001 07:03:29 -0100
Reply-To: [EMAIL PROTECTED]
Dear Joseph!
Thanks for your reply!
> The move to lambda(N) is necessary for the proof because the short cycles
> are not a result of p or q, but of the lambda reduction of them. This stems
> from the inversion of RSA (aka decryption) which requires, not knowledge of
> p or q, but knowledge of lambda(N).
Actually it's my belief, that what a "complete" argumentation should discuss
not only the order of e modulo \lambda(N) (it should be small, if you like to
mount the attack, see equation 16), but also the order of e modulo \lambda(p)
(see equation 18 & 19).
I just realized, that I had a typo in my last mail: I wrote ord (e) mod p
instead of ord (e) mod \lambda(p) = ord (e) mod p-1. Strange ... The authors
wrote mod p on page 17 too. Do I miss something? Isn't the order of e mod p
irrelevant? I need to know, when the exponent of C is equal to 1, therefore I
need to know the order e mod p-1 and/or the order of e mod \lambda(N).
I'm really lost! HELP!
> Everything else is just argument for that statement.
But is the arguemntation correct?
Best wishes,
Peter
PS: And I still don't understand this part:
"Suppose r does not divide ord(e) mod \lambda(N). It follows immediately
that e must be an r-th power mod p. This follows form Lagrange's
Theorem: ord(e) must divide p-1, and we have assumed that r divides p-1
but r does not divide ord(e). Hence e must be an r-th power mod p."
ord(e) mod \lambda(N) must divide p-1? I�m not sure if I remember
Lagrange's Theorem well... The order of a subgroup divides the order of
it�s group. Hence for every e which is coprime to \lambda(N) the order
of e mod \lambda(N) must divide the order of (Z/\lambda(N)Z)^*. This is
\phi(\lambda(N)), isn�t it? I can�t see why ord(e) divides p-1...
And further on: You say, if r and ord(e) divide both p-1 and r doesn�t
divide ord(e) than e must be an r-th power.
Sounds obvious, but why? I�m still too blind to see through.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: A future supercomputer
Date: Wed, 21 Mar 2001 10:11:15 +0100
Mok-Kong Shen wrote:
> BTW, I read that ASCI White has about 1/1000th of the estimated
> computational power of the human brain. So with Blue Gene a
> machine could have a solid foundation to attempt to compete
> with a human being.
If anybody comes up with a brain simulation of a mouse, then it makes
sense to talk about that at all.
>
> M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Defining a cryptosystem as "broken"
Date: Wed, 21 Mar 2001 10:14:45 +0100
Joseph Ashwood wrote:
>
> Of course the user will have problems. That's where well paid cryptanalysts
> come in :) I think I can say safely that we all agree that most systems
> simply haven't been designed with security in mind (I point to MS <insert
> name here/> as an example). The difference is that I did not say this is a
> countable set, only you have made that assumption about what I have said.
> What I have said is that a threat/attack model needs to be made, I have
> never said that it is an easy problem, I have never said that the set of all
> models is countable (although because I expect that they will all be finite
> in length they are not only countable but finite), I have only said that one
> needs to be constructed for the situation. Choosing the right model should
> be done for the user, in fact the programmer will fix the threat/attack
> model whether he/she knows it or not. The only decision about the
> threat/attack model that the user makes is which programs to use. I am not
> discussing an arbitrary change it at run time impossibility, I am discussing
> exactly what I have done for a period of years now, define threat/attack
> models for things, make sure at design-time (and through later review) that
> it meets that model. That is a solvable problem, the changing threat models
> based on user input is not (although a selection from a small set of them
> may be possible, see SSL as an example).
There is no question that your project/goal is very
laudable/justified and one should attempt that as far
as one can. My point is that, even after one has achieved
that goal, there yet remains certain essential uncertainty
that cannot be avoided, namely which model to choose
in a concrete application. A hypothetical analogy: Suppose
medicine could classify all diseases and give for each an
effective treatment but the diagnostic techniques remain
imperfect, i.e. a doctor cannot determine a patient's
trouble with 100% accuracy, then there still can't be
absolute guarantee that all people will be healed. I
already mentioned as example the estimation of the
computing resources of the opponent. In most cases one
never knows that for sure. One could be conservative and
think (guess) of some sort of upper bound. But that's a
subjective matter, isn't it?
M. K. Shen
------------------------------
Date: Wed, 21 Mar 2001 10:16:28 +0100
From: Daniel <[EMAIL PROTECTED]>
Subject: Re: Codes that use *numbers* for keys
You're missing the point. I doesn't matter how long you 'kana' is. It still
has a pattern, and patterns are a very bad source of entropy. For instance,
your combination is "ma-ri-ko-ha-su-wo-no-mu-ko-to-ga-da-i-su-ki-da".
Knowing this, I can figure out that the first letter is probably a consonant
and the second letter is a vowel. This information will narrow down your
keyspace rather significantly. Assuming the english language has 1.3 bits of
entropy per letter, your 'kana' has even less entropy than that. So, your
"high density" combination is easily brokable by brute-force.
For arguments sake, let say you do have 1.3 bits of entropy and remove the
'-' signs. Then you have a total of 31 characters. This adds up to the
equivalent of a 40.3 bit key, which is easily broken.
Regards,
Daniel.
Juuichiketajin wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> >
> >Juuichiketajin <[EMAIL PROTECTED]> wrote:
> >
> >
> >> Even granting that binary divisions are somehow superior, I suspect
> that the
> >> REAL reason bits are used, rather than bytes or at the very least
> nibbles, is
> >> so the sizes sound bigger.
> >> When you hear "48-bit key", don't you find yourself performing some
> mental
> >> calculation as to the value of 2^48 in some other system?
> >
> >You're somewhat right if you exchange "key" with "passphrase". In many
> >language systems, one character (like a Hiragana symbol) is represented
> >by two or more bytes, but the maximum entropy actually is defined by
> >what the user can enter, not by the number of bits used to represent
> the
> >characters. Same for plain ASCII: the user can only enter a small
> >subset of the whole character range 0...255 (or 0..127 resp.). That's
> >something an implementor has to be aware of.
> >
> >Of course, you have to hash the passphrase and try to "stretch" it.
> >Nevertheless, when the user just enters 4 or 5 symbols as passphrase,
> >the cipher will be broken by brute force attack. And as the user has to
> >be able to remember his passphrase, a clever guessing attack is likely
> >to succeed against many passphrases that are much longer. That means,
> >that in real-world applications, the theoretical keyspace is only good
> >for measuring strength against direct attacks against the possible
> keys,
> >not for measuring attacks against the passphrase.
> >
> >But in order to be aware of such issues, you need to use bits as units.
> >Heck, on a strange system, a character might even be represented as 4
> >bytes, but only 1 of them actually used. If you don't strip the
> >remaining 3 off, the attacker knows a lot of plaintext at regular
> >patterns that has been fed into the hash fuction.
> >
> >Regards,
> >
> >Erich
> I mean, you know how in a spreadsheet program, you have letters used as
> base-26 digits? I mean, use kana as base-44 (or higher) digits. And my
> guess (it is just a guess) is that it would be easy to come up with
> combinations like "ma-ri-ko-ha-su-wo-no-mu-ko-to-ga-da-i-su-ki-da" which
> are EASY to remember and have HIGH density!!!! Or is it high density?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A future supercomputer
Date: Wed, 21 Mar 2001 10:26:56 +0100
JCA wrote:
>
[snip]
> My feeling is that even if such estimates about ASCI (or Blue Gene) were
> correct, this behemoth would not be one inch closer to effectively competing
> with the human brain, except in very constrained, well-defined, rigid
> environments - something that computers have done all along anyway. Thus, if
> Deep Thought was just able to beat Kasparov, Blue Gene would probably beat
> the crap out of him. That wouldn't make it any more human though.
Note that I said only that with the power of Blue Gene
the machine starts to have a solid foundation to compete
with humans. (Up to now it doesn't have anything, because
its computing power is too small.) This is the first step.
Sciences always advance step by step. People at the
time of James Watt would certainly say that there could
never never be an engine so powerful as to enable space
flight.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: looking for "Crowds"
Date: Wed, 21 Mar 2001 10:41:28 +0100
John Savard wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >I like to remark that a primitive way of anonymous browsing
> >is to do it from an internet cafe/shop.
>
> Don't you have to give your credit card before they let you access the
> Internet?
No. One normally pays cash here. Does one have to show any
identity when one enters an internet cafe in Canada?
BTW, I think that if the internet cafes/shops would offer
web page hosting for limited time and under accounts
that are unidentifiable, e.g. numerals or anything, then
anonymous communication could be fairly perfect.
M. K. Shen
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: NSA in the news on CNN
Date: Wed, 21 Mar 2001 09:50:48 GMT
"SCOTT19U.ZIP_GUY" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I don't trust Hollywood. But its possible the precived
> view as presented by Hollywood actually casts them in
> far less evil way than they really are.
I think it far more likely that the evil intentions of the NSA have been
vastly exaggerated at best, and completely fabricated at worst, and not
only by Hollywood. I'm amazed by how much people confuse the NSA with
the CIA, too--the NSA does not have covert operations to overthrow
foreign heads of state. The NSA just digs up information and
distributes it to other "customers," who then do what they want with it;
and it also works on preventing the spooks of other countries from doing
the same.
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: NSA in the news on CNN
Date: Wed, 21 Mar 2001 09:50:53 GMT
They have a gift shop??
"JPeschel" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] writes, in part:
>
> >Those people at Fort Meade
> >must be getting desperate for funding, or something!
>
> You mean all that bread raised from selling those cool little coffee
cups,
> groovy t-shirts, and those far-out tie-dyed sweat shirts sold in
> the gift shop isn't enough funding?
>
> Joe
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
>
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: Is Evidence Eliminator at all useful ??
Date: Wed, 21 Mar 2001 01:50:35 -0800
Tom St Denis wrote:
> > Send me $125 and I'll send you my detailed report on the strengths and
> > weaknesses of Evidence Eliminator.
> Now why would I do that? :-?
When I said "you", I didn't mean you. I meant those naive new users you
were talking about. As many of them as possible.
DS
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: What happens when RSA keys don't use primes?
Date: Wed, 21 Mar 2001 09:53:09 GMT
My understanding is that RSA encryption (and some other allied
cryptosystems) depend on the use of large primes to generate keys.
However, I also understand that the methods used to generate these
primes only determine that it is "reasonably probable" that the numbers
picked are indeed prime; they do not verify that the numbers are truly
prime, as that would take too long. Given this, I find myself
wondering: What happens if the numbers are _not_ prime, however
improbable that might be? Do the encryption and decryption functions
not work at all, or do they fail intermittently, or are they simply more
vulnerable to cryptanalysis, or what?
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: What happens when RSA keys don't use primes?
Date: Wed, 21 Mar 2001 11:02:39 +0100
Mxsmanic wrote:
>
> My understanding is that RSA encryption (and some other allied
> cryptosystems) depend on the use of large primes to generate keys.
> However, I also understand that the methods used to generate these
> primes only determine that it is "reasonably probable" that the numbers
> picked are indeed prime; they do not verify that the numbers are truly
> prime, as that would take too long. Given this, I find myself
> wondering: What happens if the numbers are _not_ prime, however
> improbable that might be? Do the encryption and decryption functions
> not work at all, or do they fail intermittently, or are they simply more
> vulnerable to cryptanalysis, or what?
In my humble understanding this is all a probability issue.
If the chance that the 'believed' primes being composite
is sufficiently small, then it can be justified that one
takes the risk of the vulnerability. For a block cipher,
the opponent also has a chance of simply 'guessing' the
right key. All airplanes have some chance of crashing, yet
most people fly nonetheless.
M. K. Shen
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: What happens when RSA keys don't use primes?
Date: Wed, 21 Mar 2001 10:40:09 GMT
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In my humble understanding this is all a
> probability issue. If the chance that the
> 'believed' primes being composite is
> sufficiently small, then it can be justified
> that one takes the risk of the vulnerability.
I understand that. I just don't understand exactly what the
"vulnerability" actually is. Will the encryption/decryption
systematically break? Or will it break only occasionally, for certain
plaintexts or ciphertexts? Or will it work fine, but become very
vulnerable to cryptanalysis? Or something else?
------------------------------
From: "????" <[EMAIL PROTECTED]>
Crossposted-To: comp.security,alt.security,alt.2600
Subject: Re: I encourage people to boycott and ban all Russian goods and services, if
the Russian Federation is banning Jehovah's Witnesses .......
Date: Tue, 20 Mar 2001 12:45:45 +0200
"Viktor CK Pilpenok" <[EMAIL PROTECTED]> ??? ??????
news:968jvn$rbs$[EMAIL PROTECTED]...
> In article <96408r$csb$[EMAIL PROTECTED]>,
> Markku J. Saarelainen <[EMAIL PROTECTED]> wrote:
> >
> >
> >>> I encourage all people around the world to boycott and ban all Russian
> > >>goods and services, if the Russian Federation is banning Jehovah's
> > >>Witnesses .......
> >
> >
> >And how the .... it's related to either sci.crypt, comp.security or
> >alt.security ? maybe you plan to enccrypt the russian federation to
> >death ? or throw crypto-related papers at them ????
>
Maybe he was thinking he could use Kryptonite to remove their super-powers
But then again. They aren't a super-power any more (hehe)...
Besides it's much more logical to boycott the wit-lesses... errr the
witnesses.
Install keypads now, inplace of your door-bells. Secure all access points
against
Witness intrusion...
------------------------------
Date: Wed, 21 Mar 2001 12:50:35 +0200
From: Jyrki Lahtonen <[EMAIL PROTECTED]>
Subject: Hours of work done on RSA, ECC or NTRU ?
Hi y'all,
I was wondering whether crude estimates of the security
of the above mentioned PK systems could be obtained by
comparing the number of research hours that have been
spent in vain attempts at cracking them. Of course, a
single breakthru is worth millions of hours of banging
one's head against the wall. Nevertheless, having an
idea of the relative levels of "peer review" might be
helpful.
My gut feeling would be that RSA is the clear winner in
this race in that may be ten times more work has gone
into cracking RSA than ECC. A wild guess would be that
at least a similar gap is between ECC and NTRU (may be
even two orders of magnitude as some of the work on RSA
has undoubtedly been helpful for ECC-would-be-crackers).
I would be interested in hearing other people's opinions
on this.
So as not to hurt anyone's feelings unduly let me state the
following facts for the record:
1) The confidence level of a system doesn't grow linearly
as a function of the time spent on looking for a crack.
2) Chronological coincidences obviously have an impact on
a confidence level measure like this: RSA wins partly
because it is the oldest, NTRU suffers for being the
new kid on the block.
3) My exposure to research articles may be biased in favor
of ECC. I leave it to you to decide, whether this has
warped my gut feeling.
Thanks for your input and thoughts,
--
Jyrki Lahtonen, docent
Department of Mathematics,
University of Turku,
FIN-20014 Turku, Finland
http://users.utu.fi/lahtonen
tel: (02) 333 6014
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: How to eliminate redondancy? (moving steadily towards being computer
science terminology)
Date: Wed, 21 Mar 2001 11:31:48 -0000
<[EMAIL PROTECTED]> divulged:
> If RSA is your corner stone as to an ideal encryption
>product you have a lot to learn Joe.
actually i think joseph said that rsa is not an ideal cipher, at least
in the original form, precisely because it was bijective in the way that
you have been advocating.
--
okay, have a sig then
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => TV detection (was: FBI easily cracks encryption ...?)
Date: 21 Mar 2001 11:27:05 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Dave Howe
([EMAIL PROTECTED]) wrote:
> In our last episode (<alt.security.pgp>[19 Mar 2001 13:12:59 GMT]),
> [EMAIL PROTECTED] (Richard Herring) said :
> >In article <[EMAIL PROTECTED]>, Dave Howe
>([EMAIL PROTECTED]) wrote:
> >> flat) and really spent much of their time either at their parent's
> >> houses or otherwise occupied - and got sick of having their cupboards
> >> searched for the TV or radio set they "must" have.
> >Not that a radio would be relevant.
> *smile*
> obviously not old enough to remember when radios required a licence if
> you did not have a TV.
Oh, I remember all right. But it didn't apply by the time
students were routinely installing TVs.
I still have my family's first transistor radio - which has a
plaque to confirm that royalties were paid on the Marconi patents.
> Not sure about the current situation - But AFAIK, it was dropped
> entirely
It was. Unfortunately most UK legislation before ~1990 is not online
so I can't check which Wireless Telegraphy act dropped the radio licence.
> (a TV inspector guy tried claiming to a bunch of students
> back when I was one that the B/W tv licence was required for radios,
> but didn't come back with a policeman when he was told to bugger off.)
Not even logical. They'd have needed a *radio* licence.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Hard)
Subject: Re: What happens when RSA keys don't use primes?
Date: Wed, 21 Mar 2001 11:44:33 GMT
On Wed, 21 Mar 2001 10:40:09 GMT, "Mxsmanic" <[EMAIL PROTECTED]>
wrote:
>"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>
>> In my humble understanding this is all a
>> probability issue. If the chance that the
>> 'believed' primes being composite is
>> sufficiently small, then it can be justified
>> that one takes the risk of the vulnerability.
>
>I understand that. I just don't understand exactly what the
>"vulnerability" actually is. Will the encryption/decryption
>systematically break? Or will it break only occasionally, for certain
>plaintexts or ciphertexts? Or will it work fine, but become very
>vulnerable to cryptanalysis? Or something else?
>
That is a question I've had, too. You described it well. I wonder if
any will answer it as clearly as it was posed?
------------------------------
** 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
******************************
