Cryptography-Digest Digest #596, Volume #14 Tue, 12 Jun 01 14:13:01 EDT
Contents:
Timer chip (HyperCube)
Re: Simple Crypto II, the public key... (Anton Stiglic)
Re: BigNum Question ("Harris Georgiou")
Re: Alice and Bob Speak MooJoo (Zonn)
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY (Tim Tyler)
Re: Discrete Logarithm ("Douglas A. Gwyn")
Re: Humor, "I Must be a Threat to National Security" ("Douglas A. Gwyn")
Re: Publication violation notice ("Douglas A. Gwyn")
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and ("Douglas
A. Gwyn")
Re: Free Triple DES Source code is needed. (Mark Wooding)
Re: Lookup table for DH's prime P? (Mark Wooding)
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Re: IV (Tim Tyler)
Re: One last bijection question (Tim Tyler)
Re: Lookup table for DH's prime P? (Mark Wooding)
Re: IV ([EMAIL PROTECTED])
Re: Lookup table for DH's prime P? ("Neil Couture")
Re: Timer chip (Paul Rubin)
Re: National Security Nightmare? (Jim D)
----------------------------------------------------------------------------
Date: Tue, 12 Jun 2001 18:19:41 +0200
From: HyperCube <[EMAIL PROTECTED]>
Subject: Timer chip
Hi folks, I heard there's a way to directly access the processor's or
board's timer chip by reading out a special register or memory address.
This bypasses the common timer interrupt and should give a resolution in
times of nano-seconds(!?), of course well suited for random number
generation. Does anybody know how it is done (I mean how it is really
done, in detail)? Thanks a lot.
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Simple Crypto II, the public key...
Date: Tue, 12 Jun 2001 12:24:25 -0400
Phil Carmody wrote:
>
> OK, is there an asymmetric equivalent to the symmetric
>
> while(c=getchar()!=EOF) putchar(c^k);
Do you want something that is secure, or just something you
can do in a while loop, encrypting little chunks at a time?
If you want something secure, you can look at Goldwasser-Micali
probabilistic encryption scheme, it works like this:
choose two large primes, compute n = p*q (like in RSA).
Choose a pseudo-sqaure, y, mod n. y is a pseudo-square mod n
if Legender symbol (y,n) = 1 but y is a non-quadratic residue.
See Handbook of Applied crypto for algorithms to compute the
Lengender symbol given the factorization of n.
This is the end of the complicated part.
n, y is the public key, private key is the factors of n.
To encrypt a message m, represent it in binary m[1]m[2]...m[t]
Then:
for (i = 1; i <= t; i++) {
Pick random x \in [1, n];
if (m[i] == 1) {
c[i] = y*x^2 % n;
}
else {
c[i] = x^2 % n;
}
}
return the array c;
Of course, you can transform the above into an algo that encryptes
char by char using getchar...
Decryption is:
for (i = 1; i <= t; i++) {
e = Legender Symbol (c[i], n)
/* there exist algorithms to compute the above,
given knowledge of the factorization of n */
if (e == 1) {
m[i] = 0;
}
else {
m[i] = 1;
}
}
return the array m;
--Anton
------------------------------
From: "Harris Georgiou" <[EMAIL PROTECTED]>
Subject: Re: BigNum Question
Date: Tue, 12 Jun 2001 15:55:36 +0300
Ï Tim Tyler <[EMAIL PROTECTED]> Ýãñáøå óôï ìÞíõìá óõæÞôçóçò:
[EMAIL PROTECTED]
> Harris Georgiou <[EMAIL PROTECTED]> wrote:
> : Ï Tim Tyler <[EMAIL PROTECTED]> Ýãñáøå óôï ìÞíõìá óõæÞôçóçò:
> ........
> If there's a problem with Java's cryptography stuff, it seems to be that
> these classes are immutable, so there's no way of deleting objects - you
> can only null them, and wait for the garbage collector to clean
> up afterwards.
Not true. Of course garbage collector is there to free the programmer of
several "boring" lines of cleanup code, but there are always functions to
actually delete any object on call. Try Runtime.gc() and destroy() and
delete() methods in various objects.
--
Harris
- 'Malo e lelei ki he pongipongi!'
------------------------------
From: Zonn <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Tue, 12 Jun 2001 16:39:42 GMT
On Tue, 12 Jun 2001 10:06:59 -0400, in sci.crypt, "Robert J. Kolker"
<[EMAIL PROTECTED]> wrote:
>"Douglas A. Gwyn" wrote:
>
>> Boyd Roberts wrote:
>> > "Tom St Denis" <[EMAIL PROTECTED]> a écrit:
>> > > How would a blind person learn to speak?
>> > verbal feedback. it's a bootstrap problem.
>>
>> Note that Helen Keller learned to communicate despite
>> being deaf, dumb, and blind. But it wasn't easy.
>
>1. Keller was not always blind and deaf. I think she
> was rendered so by an acute bout with scarlet
> fever or measles.
>
>2. She learned to "speak" through her remaining spatial
> sense, i.e. her sense of touch.
3. Helen Keller could in no sense of the word be considered "dumb". (Refer to #2
above.)
-Zonn
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 16:13:39 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> : John Savard wrote:
:> :> It is not surprising, however, that today cryptography is concerned
:> :> mainly with an area about which Shannon said little, other than to
:> :> give it a name: the work factor. Particularly as the extreme utility
:> :> (and practicality, and convenience) of the 'public-key' methods has
:> :> made them central to most modern employment of cryptographic
:> :> techniques, despite the fact that their security, in the
:> :> information-theoretic sense, is precisely nil.
:>
:> : But, if something that is practically secure is of
:> : precisely nil security in the information-theoretical
:> : sense, that means a big contradiction to intuition/
:> : common-sense, isn't it? [...]
:>
:> All the information necessary to read a public key message
:> resides in a combination of the message and the public key - and
:> both should be considered to be available to the attacker.
:>
:> If only he could factor (or whatever) the public key he would
:> be able to read the message. He has all the information necessary
:> to do this at his disposal - but alas, the task takes a lot of effort
:> to perform.
:>
:> The "information-theoretic" security of such a system can
:> usefully be though of as being nil.
: But measures should have adquate (intuitionally reasonable)
: interpretations, I suppose. If a security measure
: says 0 security, then one would 'very naturally' think
: that that means no protection at all, isn't it?
That's why I qualified what sort of security was under discussion.
"Information-theoretic" security is what you need *if* you face a
computationally unbounded attacker.
Nil protection is what you get if you use RSA in the face of such an attacker.
For the more common type of attacker, "work factor" security may be enough.
One of the problems with "work factor" security is that it's commonly
very hard to measure. No-one knows that the "work factor" security
of RSA, or AES is, for example.
That's one reason why "information-theoretic" security can be desirable -
you can actually measure it.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Discrete Logarithm
Date: Tue, 12 Jun 2001 15:43:26 GMT
Tom St Denis wrote:
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote...
> > JCKW wrote:
> > > I would like to know how i can solve the integer discrete logarithm
> > > problem:
> > Gee, so would I.
> Not a polite way to deal with a badly phrased question. Tisk tisk.
Hm, I see you're humor impaired.
------------------------------
Crossposted-To: comp.security.misc
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Humor, "I Must be a Threat to National Security"
Date: Tue, 12 Jun 2001 15:47:09 GMT
"SCOTT19U.ZIP_GUY" wrote:
> ... I don't see why you where not hired but it may mean
> your to honest or you may not have matched the religion
> of the ones who you interviewed with. Its possible they
> had a quota for women at the time you applied.
Most likely, the available positions had more qualified
applicants. From the tone of some of Boney's narrative,
I suspect they are glad they didn't hire him..
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Publication violation notice
Date: Tue, 12 Jun 2001 15:52:17 GMT
Paul Rubin wrote:
> someone tried to send a chess openings book to a prisoner, and the
> prison refused delivery because it "contained code throughout".
Not surprising. Censors in general (e.g. postal censors during
wartime) have to have some such policy, because it is in fact
easy enough to encrypt messages within such schemes, and the
censors don't have the resources to try to analyze the material
closely enough to ensure that nothing is hidden within.
In the case of a printed book from a well-known publisher,
there is less chance of this than in a privately printed copy,
but policies like this one tend to err on the side of caution.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Tue, 12 Jun 2001 16:18:08 GMT
Mok-Kong Shen wrote:
> One could say that Whitehead and Russell had persued the
> 'wrong' goal and failed. But then which goal was/is
> instead 'the' 'right' one? Could anyone say that? I am
> not sure that one can.
Sure we can. In this particular case, we now know that
the program could not be completed, not even in principle.
> ... Do you think there is
> always ground to blame, when a scientist fails to
> achieve or fully achieve his goal?
You're making something out of this that I never intended.
Recall that what I said was:
> PM is famous because it was an ambitious attempt to
> implement a model of mathematics which we now know
> to be wrong.
What specifically is objectionable in that?
> > A major motivator was the hope that thereby all antinomies
> > could be eliminated. But the mechanism introduced for
> > that purpose was awkward and unnatural. Today we take
> > different approaches for such matters. For example:
> > Tightest form of antinomy: "This statement is false."
> > Is that statement true or false, or neither, or what?
> > A simple, *stable* solution is to treat the truth value
> > on a continuum, or in other words, to apply fuzzy logic;
> > then the statement has a truth value of (true+false)/2,
> > which is 0.5 using true=1 and false=0, or 0 using
> > true=1 and false=-1. (There is a theorem to the effect
> > that this approach solves all logical antinomies.)
> > There is actually a connection with cryptanalysis lurking
> > in this approach, in that one can treat Boolean variables
> > as fuzzy; then a *mutually contradictory* or "incorrect"
> > (according to "hard" logic) assignment of values to
> > variables no longer stymies further solution. (Think
> > eigenvalue convergence, etc.)
> There are in fact many many kinds of logics. Fuzzy logic
> is only one of that many many, though due to practical
> applications many engineers are nowadays also quite
> knowledgeable in that. There is nothing that could be
> regarded as 'the' logic. The 'diversity' is very high
> and only comparatively few real specialists in logics
> could oversee the entire field. (I was so told by a
> person who has studied math and apparently has delved
> quite a bit into logics). My knowledge in logics is
> very meager. (Excepting some familiarity with automated
> deduction, my current knowledge in logics is practically
> null.) Hence I have a possibly very very dumb question:
> Does the theorem you mentioned have essential
> implications to the other subfields of logics or is it
> limited in its significance to fuzzy logic? If the
> former case, in which sense/manner would be its impact?
I'm well aware of the variety of "logics". However, the
class of fuzzy logics (differing only in the exact formulae
for the result on a combining operator) are especially
applicable to such problems, and as I indicated, allow real
implementations of solutions to very real problems.
My original point in this regard was that we have more
useful ways of resolving antinomies than PM's ramified
theory of types.
> And could you also give a pointer (book, page number)
> to the theorem?
Not right away, but it's probably mentioned in Kosko's book.
It's pretty obvious if you have much experience with convexity.
> > > He attempted to axiomatize the whole of mathematics
> > > but failed. But that does not mean that anything he
> > > wrote is wrong.
> > I don't think that is the thrust of Bourbaki. As I see it,
> > it was to provide rigorous developments of the "standard"
> > content of mathematics.
> As far as I know, Bourbaki wanted to somehow encompass ALL
> fields of math from a certain common (unified) structural
> point of view. But some new (some yet developing) subfields
> apparently couldn't be readily put to fit well with such
> a common scheme, so he finally had to give up. I am not a
> mathematician and haven't closely followed the issue, so
> I can't ensure that this view is entirely correct. But I
> strongly believe that his failure to achieve his goal was
> because he was too ambitious (having set too high a goal).
? Bourbaki's books have served well as references for many
years. That is not a "failure", especially as I understand
the goal. This is to be contrasted with PM, which has been
used for almost nothing since its publication. (I am aware
of at least one significant paper that used PM's notation
simply as a standard example, for purpose of Goedel-numbering,
but any sufficient, notation for number-theoretic proof would
have served as well.)
> I don't think that I understand your notion of 'standard
> content' of math. In which sense is an 'arbitrary'
> subfield (or materials of a subfield) of math 'standard'?
I don't know where "arbitrary" came from.
"Standard content" means what the mathematics community
reasonably expects to be taught to all future mathematicians.
This naturally evolves over time, but always includes
such areas as analysis, topology, basic abstract algebra,
etc. There is not much "arbitrariness" about the selection;
it consists of that which helps in learning other, more
advanced areas.
> Any contemporary branch of math, classical or modern,
> theoretical or applied, is in my view rigorously founded
> and developed. (There is no snakeoil like in crypto.)
> So rigor has certainly always been there, whether there
> was Bourbaki or not.
Sorry, no.
Or rather, while modern mathematicians are much better
aware of the need for rigor than were those of over a
century ago, a lot of their actual work is not conducted
to the standard of rigor that is currently considered
essential in a published paper. Rigor is applied after
the fact, in many cases. And there have been numerous
errors in technical mathematical papers, sometimes fixable
and sometimes fatal.
By the way, my views on Bourbaki are influenced by having
read what some of its members have said.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Free Triple DES Source code is needed.
Date: 12 Jun 2001 17:01:57 GMT
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> Actually if you format your C code properly, then C is a strict subset of
> C++
No! This just isn't true. The following is *correct* idiomatic C:
#include <stdlib.h>
#include <string.h>
char *mystrdup(const char *p)
{
size_t sz = strlen(p) + 1;
char *q = malloc(sz);
if (q) memcpy(q, p, sz);
return (q);
}
This will not compile under a C++ compiler (you're not allowed the
implicit cast from `void *'). In C, it's bad form to insert the
explicit cast because it hides the error of failing to include
<stdlib.h>.
Other examples:
* C's complex number support is utterly incompatible with C++'s.
* C allows variable-length arrays (declared with a non-constant number
of elements).
C and C++ are different languages. They are evolving separately.
`C/C++' is a nonsense.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Lookup table for DH's prime P?
Date: 12 Jun 2001 17:08:17 GMT
quequ <[EMAIL PROTECTED]> wrote:
> in DH protocol the 1024bit prime P and the generator G are public values,
> it's right?
Yes.
> In this case can I use a lookup table for P (with 1000-2000 germain
> primes, for example) and a fixed generator G (G = 4)??
> This seems to be a very fast solution, because P take some minutes to
> generate on my machine (K7-500), but is this a safe way to follow?
I don't see why you need more than one prime.
-- [mdw]
------------------------------
Subject: Re: Alice and Bob Speak MooJoo
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 13:14:02 -0400
Zonn <[EMAIL PROTECTED]> writes:
>
> 3. Helen Keller could in no sense of the word be considered
> "dumb". (Refer to #2 above.)
``Dumb'' is an English word, which means ``unable to speak.''
Len.
--
Frugal Tip #34:
Use the stale Cheetos you find between your sofa cushions as an
inexpensive meat extender.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: IV
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 16:50:56 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:>> [CTR mode]
:>
:> If you have a known plaintext, you can extract the entire keystream.
: No you can't. You can only extract the portion of the keystream which
: corresponds to the known bits.
Well yes, obviously only the section corresponding to the message.
:> You can then forge messages of that length, resulting in apparently
:> sensible messages from the POV of the recipient.
: Not quite--you can change THAT PORTION of the ciphertext stream to
: anything you want. [...]
Yes - you can make any message you like of that length, and send it.
Alternatively, it is likely that you could make a number of smaller
messages - though this may depend on the exact details of the
implementation of CTR mode.
: The same weakness, BTW, applies to *all* synchronous stream ciphers.
: Indeed, it applies to the OTP [...]
Yes indeed.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One last bijection question
Reply-To: [EMAIL PROTECTED]
Date: Tue, 12 Jun 2001 16:59:50 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Mark Wooding wrote:
:> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> > These terms are explained in most textbooks on algebra, I
:> > suppose. BTW, in terminology questions, I find it mostly very
:> > practical to take a good dictionary/encyclopedia of math.
:>
:> The reason we're in this mess is that different books give different
:> definitions. [...]
: Could you please cite one book where the word 'image'
: thoroughly replaces 'range' or where the word 'range'
: would lead to ambiguity? [...]
I don't know about books - but the words are very frequently used
as synonyms - e.g.:
``The codomain or range of R, written range(R), is the set of elements t
T such that (s, t) R for some s.''
- http://www.depaul.edu/~jriely/535/book/02.pdf
``The domain of the composition f g is the domain of g, the codomain (or
range) of this composition is the codomain (or range) of f [...]''
- http://www.orst.edu/instruct/mth251/cq/FieldGuide/composition/lesson.html
``the domain and codomain (range) are swapped [...]''
- http://math.boisestate.edu/~holmes/M387syllabus/node54.html
...etc.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Lookup table for DH's prime P?
Date: 12 Jun 2001 17:26:36 GMT
Anton Stiglic <[EMAIL PROTECTED]> wrote:
> Any element != 1 and p-1 will generate a large enough group, so G = 4
> will work.
If p = 2 q + 1, where both p and q are prime, then the element 4 + pZ
has order q in the ring Z/pZ. (I'll omit the tedious pZ stuff in the
following.)
Proof: q >= 2, so p >= 5. The order of 2 must be a factor of 2 q. But
q is prime, so the only orders are 1, 2, q, or 2 q. But 2 != 1 and 2^2
= 4 != 1, so the order must be q or 2 q. In either case, the order of 4
= 2^2 is q.
-- [mdw]
------------------------------
Subject: Re: IV
From: [EMAIL PROTECTED]
Date: 12 Jun 2001 13:33:00 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
> [EMAIL PROTECTED] wrote:
>: Tim Tyler <[EMAIL PROTECTED]> writes:
>:> You can then forge messages of that length, resulting in apparently
>:> sensible messages from the POV of the recipient.
>:
>: Not quite--you can change THAT PORTION of the ciphertext stream to
>: anything you want. [...]
>
> Yes - you can make any message you like of that length, and send it.
ONLY if you send the replacement message instead of the original.
Resending it at a later time will do no good: if the forged message is
not sychronized with the keystream, then it will decrypt to gibberish.
Len.
--
I defy him to quote even a single example of an ``obvious error'' in
anything I've ever written.
-- Dan Bernstein
------------------------------
Reply-To: "Neil Couture" <[EMAIL PROTECTED]>
From: "Neil Couture" <[EMAIL PROTECTED]>
Subject: Re: Lookup table for DH's prime P?
Date: Tue, 12 Jun 2001 13:39:15 -0400
Just a little question about your implementation:
is it all your own, i mean when you said that it's not very fast?
'cos i'm using OpenSSH to get my Diffie Hellman p and g
parameters and 1024 bits is done well under one minute.
Penthium III 677 mhz 128 M.
OpenSSH gives you all theses 'cryptographic primitives' that you might
need as an API ( i use this in conjonction with the Java crypto API ).
Also it can generate c/c++ code from newly created
parameters
Neil
"quequ" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> Hi,
> I'm still working on an implementation of DH algorithm and have a new
> little question:
>
> in DH protocol the 1024bit prime P and the generator G are public values,
> it's right?
> In this case can I use a lookup table for P (with 1000-2000 germain
> primes, for example) and a fixed generator G (G = 4)??
> This seems to be a very fast solution, because P take some minutes to
> generate on my machine (K7-500), but is this a safe way to follow?
>
> thanks to all
>
> quequ
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Timer chip
Date: 12 Jun 2001 11:02:06 -0700
HyperCube <[EMAIL PROTECTED]> writes:
> Hi folks, I heard there's a way to directly access the processor's or
> board's timer chip by reading out a special register or memory address.
> This bypasses the common timer interrupt and should give a resolution in
> times of nano-seconds(!?), of course well suited for random number
> generation. Does anybody know how it is done (I mean how it is really
> done, in detail)? Thanks a lot.
It's processor and hardware specific but generally it's done by having
a CPU cycle counter on the processor. Every clock cycle (500 mhz
would mean every 2 nanoseconds), the counter gets incremented; and
there's a machine instruction for reading the counter. See for
example the RTDSC instruction on Pentium processors.
------------------------------
From: [EMAIL PROTECTED] (Jim D)
Subject: Re: National Security Nightmare?
Date: Tue, 12 Jun 2001 18:05:00 GMT
Reply-To: Jim D
On Tue, 12 Jun 2001 02:34:48 +0200, "Boyd Roberts" <[EMAIL PROTECTED]>
wrote:
>"Mok-Kong Shen" <[EMAIL PROTECTED]> a écrit dans le message news:
>[EMAIL PROTECTED]
>> In France I heard that there is a national instute
>> that decides authoritatively on language issues of French.
>
>yes, you are referring to L'Académie Française.
>
>what a waste of space. here is two of the more recent
>and totally stupid rulings they made:
>
> CD -> cédé
> [e]mail -> mél
>
>both CD and mail had been in current use for years.
In America, maybe. It's just that, like me, they object
to their language being polluted by Americanisms.
>> Is there a similar one for the English world?
There ought to be. In the UK at least.
--
______________________________________________
Posted by Jim D.
Propino tibi salutem !
jim @sideband.fsnet.co.uk
dynastic @cwcom.net
___________________________________
------------------------------
** 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
******************************
