Cryptography-Digest Digest #234, Volume #12 Sun, 16 Jul 00 14:13:01 EDT
Contents:
Re: Quantum Computing (Was: Newbie question about factoring) (Nick Maclaren)
Re: unambiguous polynomial computation and crypto ("Trevor L. Jackson, III")
Hashing Function (Simon Johnson)
Re: Quantum Computing (Was: Newbie question about factoring) (Jeffrey Shallit)
Re: Win2000 Encryption (Simon Johnson)
Re: unambiguous polynomial computation and crypto (David A Molnar)
Re: Has RSADSI Lost their mind? (DJohn37050)
Re: what is the symmetric algorithm for protection of classified info by gov
agencies ? ([EMAIL PROTECTED])
Re: Diffie Hellman Primes : Speed Tradeoff Q (Bob Silverman)
Re: Has RSADSI Lost their mind? (Roger Schlafly)
Re: Win2000 Encryption (Mack)
Re: Has RSADSI Lost their mind? (Bill Unruh)
Re: Crypto jokes? (potentially OT) (Steve Meyer)
Re: research on cryptography (Steve Meyer)
Re: Diffie Hellman Primes : Speed Tradeoff Q (Mark Wooding)
Re: Win2000 Encryption (Jerry Coffin)
Re: SECURITY CLEAN freeware text editor in win95 ? (Chem-R-Us)
Re: what is the symmetric algorithm for protection of classified info by gov
agencies ? (Jerry Coffin)
Re: Still another uncommon number transformation scheme (Mok-Kong Shen)
Re: Hashing Function (Mok-Kong Shen)
Re: SECURITY CLEAN freeware text editor in win95 ? (Jerry Coffin)
Re: Hashing Function (Mok-Kong Shen)
Re: Hashing Function (Mok-Kong Shen)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 16 Jul 2000 10:14:35 GMT
In article <8kqo60$o3i$[EMAIL PROTECTED]>,
Jeffrey Shallit <[EMAIL PROTECTED]> wrote:
>In article <8kpind$ek2$[EMAIL PROTECTED]>,
>Nick Maclaren <[EMAIL PROTECTED]> wrote:
>>
>>Oh, hell, OF COURSE a finite automaton can generate such things if
>>you allow it to be fed an infinite input tape or use an infinite
>>working tape (in the Turing model)!
>
>It's not being fed an infinite input tape. As I explained, to get
>the i'th digit, you feed the automaton with the base-k expansion of i.
It is being fed an arbitary member out of an infinite set of bounded
base tapes. This is equivalent to feeding it an infinite input tape.
For any fixed bounded size inputs, you can get only a fixed set of
set of bounded size outputs - i.e. a rational number.
>>There are lots of other similar
>>models, such as the one where the input is a true random sequence of
>>bits. That can clearly generate the expansion of ANY real number,
>>provided that you don't want any particular one :-)
>
>You misunderstand the model. It has nothing to do with random inputs.
Consider the trivial variation, where the system is fed the base k
expansion of the positive integers i, in an arbitary order. Not
so very different, is it?
The point is that, by extending a true finite automaton with a
single, specific oracle, you can get quite a few interesting and
many uninteresting models. You have given one example; I gave
another; whether any can be called finite state machines is moot.
>And the interesting point is that such a model is conjectured to generate
>only rational or transcendental numbers.
That is an interesting aspect, true.
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
Date: Sun, 16 Jul 2000 06:37:13 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: unambiguous polynomial computation and crypto
David A Molnar wrote:
[snip introduction to UP]
> Why do we even care, you ask?
>
> Because you can show that
>
> (1) one way functions exist if and only if P != UP
>
> whereas we do NOT know any such result for P != NP.
Could you mention a reference for (1) ?
------------------------------
Subject: Hashing Function
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 16 Jul 2000 04:37:16 -0700
Although this hashing method is really impractical, i thought
i'd tie up what i have learnt about primitive elemets GF(P) and
design a simple ( though it's probably been done before ) hasing
algorithm.
We first start by picking a random strong prime , P, which is at
least 128-bits long. We then pick a generator, G, at random
(this is easy since exactly half of the elements in GF(P) are
primitives)
To hash a document we divide the plain-text into blocks of
length of equal to the max size of p. We then do the following
for I number of blocks:
For i = 1 to number of blocks
Q = g^(Plain-text_i) mod p
Hash = (Hash + Q) mod p
Though very slow, it does have some nice properties, e.g. We
know for every plain-text length of one block has its own
individual hash i.e. Collision rate is the lowest possible.
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Jeffrey Shallit)
Crossposted-To: comp.theory
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: 16 Jul 2000 11:35:14 GMT
In article <8ks1ub$4un$[EMAIL PROTECTED]>,
Nick Maclaren <[EMAIL PROTECTED]> wrote:
>
>It is being fed an arbitary member out of an infinite set of bounded
>base tapes. This is equivalent to feeding it an infinite input tape.
No, it's not. Finite automata on infinite words are well studied
(e.g. Buchi automata), and the two models are not equivalent.
>The point is that, by extending a true finite automaton with a
>single, specific oracle, you can get quite a few interesting and
>many uninteresting models. You have given one example; I gave
>another; whether any can be called finite state machines is moot.
No, the machine is not extended with an "oracle" in the way that word is
generally understood by the theoretical computer science community.
The underlying machine in the model I have described *is* a finite
automaton, and *is* understood to be one by everyone who actually
writes papers on it. Of course, if you wish to use your own private
terminology, be my guest, but don't expect those who are familiar with
the area to waste much time correcting you.
Jeffrey Shallit, Computer Science, University of Waterloo,
Waterloo, Ontario N2L 3G1 Canada [EMAIL PROTECTED]
URL = http://www.math.uwaterloo.ca/~shallit/
------------------------------
Subject: Re: Win2000 Encryption
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Sun, 16 Jul 2000 05:24:18 -0700
Does anyone know which algorithm Win2000 uses?
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: unambiguous polynomial computation and crypto
Date: 16 Jul 2000 12:44:06 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> David A Molnar wrote:
> [snip introduction to UP]
>> Why do we even care, you ask?
>>
>> Because you can show that
>>
>> (1) one way functions exist if and only if P != UP
>>
>> whereas we do NOT know any such result for P != NP.
> Could you mention a reference for (1) ?
There's a proof of this on pages 283 - 284 of Papadimitriou's
_Computational Complexity_.
David Wagner has pointed out that the course notes URL I gave
in the post does not work; I used the Google cache instead of
the actual URL (a search for "unambiguous polynomial computation").
Those notes gave the same proof. I'm a little pressed for time
right now or I'd reproduce it here, sorry.
I noticed that I have another book which covers the subject
in slightly more depth -- an article on "Complexity Issues in
Cryptography" by Alan Selman as part of vol. 38 of the AMS's
_Symposia in Applied Mathematics_.
The original paper which proved it was
J. Grollman and A.L. Selman "Complexity measures for public-key
cryptography," SIAM J Computing 17 pp309-335 1988.
which is apparently the journal version of a paper in
the 1984 IEEE Foundations of Computer Science conference.
-David
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: Has RSADSI Lost their mind?
Date: 16 Jul 2000 13:28:08 GMT
There is more information that what is normally revealed about pernding
patents.
Don Johnson
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: alt.privacy
Subject: Re: what is the symmetric algorithm for protection of classified info by gov
agencies ?
Date: Sun, 16 Jul 2000 14:31:43 +0100
On Sat, 15 Jul 2000 00:59:06 -0600, Jerry Coffin <[EMAIL PROTECTED]>
wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>says...
>> FIPS 46-2, The Data Encryption Standard (DES), is the approved symmetric
>> algorithm for protection of sensitive but unclassified information by
>> government agencies.
>>
>> what is the symmetric algorithm for protection of classified info by gov
>> agencies ?
>
>There is not simply one algorithm for protection of all classified
>data, or anywhere close to it.
>
>About the only dependable source of specific information about a
>specific encryption algorithm is going to be direct from the NSA
>when/if they believe you need to know about it.
>
>If you want general information about how the NSA designs ciphers,
>consider looking at SkipJack. Though _it's_ not approved for
>classified data, I'd almost bet that they have similar ciphers that
>are, adjusted (larger key, larger S-boxes, more rounds, etc.) to
>provide the level of security they consider necessary.
There have been some embarrassing stories in the past few months about
laptop computers belonging to MI5 operatives being lost. IIRC none of
the data on them was encrypted!
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: Sun, 16 Jul 2000 14:19:52 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Mark Wooding) wrote:
> Bob Silverman <[EMAIL PROTECTED]> wrote:
> > In article <[EMAIL PROTECTED]>,
> > [EMAIL PROTECTED] (Mark Wooding) wrote:
>
> > Huh? Z/pZ* isn't cyclic.
>
> Yes it is.
You are 100% correct. I had left off part of what I intended to
write; very careless of me. I meant to write Z/(p-1)/qZ* or
(Z/pZ)* / (Z/qZ), the projective subgroup when you mod out by q.
This is the part whose structure is determined by R.
This is the part of Z/pZ* that is not in the cyclic group mod q.
> I'm considering a cryptosystem whose security is based on the
difficulty
> of a discrete logarithm problem: given primes p and q, where p = q R
+ 1
> for some composite R, with p large enough that the Number Field Sieve
is
> impractical for computing discrete logs mod p' for random primes p' of
> the same size as p, and q large enough that collision-finding
algorithms
> such as Pollard's rho are impractical for computing discrete logs in
the
> order-q subgroup of GF(p), what constraints are there on the structure
> of R such that, with current algorithms, computing discrete logs in
the
> order-q subgroup is impractical?
None. The Pollard Rho attacks on the order q subgroup do not
depend on R.
--
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/
Before you buy.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Has RSADSI Lost their mind?
Date: Sun, 16 Jul 2000 07:31:12 -0700
DJohn37050 wrote:
> There is more information that what is normally revealed about pending
> patents.
Normally, for whom? The point is that your statement was incorrect.
You said that the Certicom patent claim were on the P1363 web site.
They are not.
So whom are you comparing Certicom to? Euro patent applications are
published after 18 months. Those wishing to sell a technology often
have to reveal what they are claiming. Those with claims against
practice of standards usually have to reveal them as well.
I'm sure you will argue that Certicom is legally entitled to keep
its submarine patent applications secret. Perhaps. But please don't
pretend that the claims are on the P1363 web site, because they are
not. Certicom's letter does not tell very much about what parts of
the standard it is trying to claim.
------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: Win2000 Encryption
Date: 16 Jul 2000 14:55:05 GMT
>> >Are you saying that it should have been encrypted like it reported?
>> >
>>
>> No to tell if it is actually encrypted, you would have to
>> examine it using some sort of disk editor. As long as you copy with
>> Win2k running it will convert it to the unencrypted form.
>
>
>So it is only encrypted on the HD, but when NT using NTFS drivers
>reads it off the HD it is decrypted and thus I never see the
>cipher text of the file (unless I bypass NT and use a disk
>editor like you say)?
When you use NT to download it over the network it is using
the Win2k drivers on the computer you are downloading it off of.
Unless the computer is set up as dual boot and you are
actually doing this under NT workstation.
>
>How can I be sure that it is encrypted? This is a very interesting
>puzzle...
>
Learn the file system and go in with a disk editor (from dos) and
check the appropriate blocks. Or simply search the disk drive
for some text from the file in question (the easy way). For example
if we know the file contains "this is a test". Search the drive for that
string but be aware that the swap file may also contain the data.
Does anyone know if win2k does swap file erasure at shutdown?
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: Has RSADSI Lost their mind?
Date: 16 Jul 2000 16:09:45 GMT
In <[EMAIL PROTECTED]> Roger Schlafly <[EMAIL PROTECTED]>
writes:
]DJohn37050 wrote:
]> To see Certicom patent claims, see IEEE P1363 website.
]Are you referring to this letter?
]http://grouper.ieee.org/groups/1363/P1363/letters/Certicom.txt
]This has no patent claims. It references a couple of issued patents,
]and those claims are publicly available, of course. But there is no
]description of what is being claimed in Certicom patent applications.
That letter is incredible. Absolutely everything there sounds like
algorithms, which cannot be patented.
------------------------------
From: [EMAIL PROTECTED] (Steve Meyer)
Subject: Re: Crypto jokes? (potentially OT)
Reply-To: [EMAIL PROTECTED]
Date: 16 Jul 2000 16:33:41 GMT
Are you saying that Feyerabend's argrument that study of
Computer Science in EE departments is impossible is wrong, i.e.
impossibility of the normal scientific activity of
discovery attribution? See Feyerabend, P., "Science in
A Free Society", NLB, London, 1978, p. 154. Feyerabend
witnessed the annexation of the Berkeley L&S Computer Science
Department by the EE department.
On Wed, 12 Jul 2000 23:11:33 -0400, Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>
>I didn't understand your joke. Is it that you really are unaware
>that nonsecret-key encryption had in fact been invented before RSA?
>(However, it wasn't much exploited.)
>Steve Meyer wrote:
>> How about claim by BBC television producer that English spy ageny
>> discovered public key cryptography. Probably in joke that one must
>> attend IACR conference to appreciate.
------------------------------
From: [EMAIL PROTECTED] (Steve Meyer)
Subject: Re: research on cryptography
Reply-To: [EMAIL PROTECTED]
Date: 16 Jul 2000 16:51:12 GMT
You might look at working on the PPP problem (permuted Perceptron Problem).
It is a seemingly simple problem that may be of interest in other areas
of computer science. See Knudson, L. and Meier, W. "Cryptanalysis of an
Identification Scheme Based on the Permuted Perceptron Problem. from
1999 Eurocrypt (published as Springer Lecture Notes in Computer Science
volume), pp 363-374.
On Mon, 3 Jul 2000 23:01:55 +0800, Foo Kim Eng <[EMAIL PROTECTED]> wrote:
>I am a physics B.Sc graduate, with some knowledge in mathematical physics
>and qbasic programming, looking for a master project in the field of
>cryptography. I don't know anything specific about cryptography (except the
>most general knowledge), can anyone here give me some suggestion or commend
>about the background needed to success for my purpose? What is the frontier
>achievement in this area and the topics or scopes which still can put our
>effort into it?
>Thanks.
>
>
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Diffie Hellman Primes : Speed Tradeoff Q
Date: 16 Jul 2000 16:56:59 GMT
Bob Silverman <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (Mark Wooding) wrote:
[p = q R + 1...]
> > what constraints are there on the structure of R such that, with
> > current algorithms, computing discrete logs in the order-q subgroup
> > is impractical?
>
> None.
That's a good answer. I like that answer a lot...
> The Pollard Rho attacks on the order q subgroup do not depend on R.
... but this is an incomplete justification for it.
I understand how Pollard rho works. I took the time to implement it in
a particularly bored moment a week or two ago.
I'm more interested in whether there are other known attacks against
this sort of structure. For example, if it were possible to compute
discrete logs mod p = q R + 1 then that easily extends to finding
discrete logs in the q-order subgroup.
Let's make this really easy. Suppose R = 2^n for some integer n. Does
that make the scheme insecure? (Remember that p is still large enough
that random primes of the same size are secure.)
[I think the lesson to me is that I should actually read up on the NFS
myself. That sounds like a good idea.]
-- [mdw]
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: Win2000 Encryption
Date: Sun, 16 Jul 2000 11:01:55 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ ... ]
> Does anyone know if win2k does swap file erasure at shutdown?
It can, but it doesn't necessarily. Whether it does or not can be
set either as a policy for an entire domain or as a setting local to
a particular computer.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
Date: Sun, 16 Jul 2000 10:05:54 -0700
From: Chem-R-Us <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy
Subject: Re: SECURITY CLEAN freeware text editor in win95 ?
Fafnir wrote:
>
> Yeah, but some of us need an os that can actually get things done.
Obviously you know little about operating systems. Linux workstations
are every bit as capable as any other workstation, more so than a
gatesware toy-station!
--
Chem-R-Us
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy
Subject: Re: what is the symmetric algorithm for protection of classified info by gov
agencies ?
Date: Sun, 16 Jul 2000 11:12:30 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
[ talking about Skipjack and such ]
> There have been some embarrassing stories in the past few months about
> laptop computers belonging to MI5 operatives being lost. IIRC none of
> the data on them was encrypted!
This brings up a point worth making more clear: a great algorithm
embedded into software that's a pain to use will often provide FAR
less real security than a less-secure algorithm implemented in
software that's enough easier to use that people will actually use it
dependably.
Obviously, it's best to start with a really superb algorithm and then
implement it in a program that's really easy to use, but that's not
always available.
Of course, security is nearly always at least something of a pain,
and it's up to the diligence of the security officer to ensure that
things really do get done. If he's lax, even really nice programs
won't be used dependably. At the same time, even a truly superb
security officer will have more than he can handle if the available
software is sufficiently difficult and painful to use.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Still another uncommon number transformation scheme
Date: Sun, 16 Jul 2000 19:25:19 +0200
Addendum:
There is room to add some 'complexities' into the scheme.
One can e.g. use U1, with U1 = a*U + b mod p, in place of
U in the processing, where a and b are arbitrarily chosen.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hashing Function
Date: Sun, 16 Jul 2000 19:25:46 +0200
Simon Johnson wrote:
> [snip]
> (this is easy since exactly half of the elements in GF(P) are
> primitives)
'exactly half' is not true.
M. K. Shen
------------------------------
From: Jerry Coffin <[EMAIL PROTECTED]>
Subject: Re: SECURITY CLEAN freeware text editor in win95 ?
Date: Sun, 16 Jul 2000 11:18:32 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> thanks,
>
> I will stay in 30 kb limitation of notepad [ it is very clean ] ...
> for other staff, EditPad 351 [ it creates / deletes intermittent temp files ]
Simply deleting a temp file is rarely sufficient to accomplish much
of anything: you need to ensure that the disk space the temp file
occupied is overwritten with some other information. Unfortunately,
simply seeking back to the beginning of the file and changing the
data may not be sufficient for this task on all systems. In
particular, if the temp file was compressed, the new data may end up
more or less compessible than the old. If it's more compressible, it
won't necessarily occupy all the space that the old did, and will
leave parts of the old file intact.
I'm not sure about NTFS in particular, but if the new data is less
compressible than the old, things could actually be even worse: a
file system might attempt to minimize fragmentation by moving the new
data to an entirely different area of disk space to allowing writing
it in a contiguous chunk.
To have a reasoanble assurance of secure erasure, you need to get the
FS to tell you what parts of the disk are occupied by the temp file,
and then overwrite those parts of the disk.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hashing Function
Date: Sun, 16 Jul 2000 19:30:38 +0200
Mok-Kong Shen wrote:
> Simon Johnson wrote:
>
> > [snip]
> > (this is easy since exactly half of the elements in GF(P) are
> > primitives)
>
> 'exactly half' is not true.
Sorry, I overlooked your assumption.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hashing Function
Date: Sun, 16 Jul 2000 20:15:08 +0200
Simon Johnson wrote:
> We first start by picking a random strong prime , P, which is at
> least 128-bits long. We then pick a generator, G, at random
> (this is easy since exactly half of the elements in GF(P) are
> primitives)
>
> To hash a document we divide the plain-text into blocks of
> length of equal to the max size of p. We then do the following
> for I number of blocks:
>
> For i = 1 to number of blocks
> Q = g^(Plain-text_i) mod p
> Hash = (Hash + Q) mod p
>
> Though very slow, it does have some nice properties, e.g. We
> know for every plain-text length of one block has its own
> individual hash i.e. Collision rate is the lowest possible.
If p is a 128 bit prime, is your block size also 128 bit? How does
one go about to prove the claim about the collision rate?
M. K. Shen
------------------------------
** 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
******************************
