Cryptography-Digest Digest #74, Volume #14 Wed, 4 Apr 01 08:13:01 EDT
Contents:
Factoring.... ("Jeffrey Walton")
Re: A group ? ("Jack Lindso")
Re: efficient rabin signature? (Bryan Olson)
Clarification - Re: Factoring.... ("Jeffrey Walton")
Re: How do I exchange the values of A and B (Stefek Zaba)
Re: Factoring.... ("Tom St Denis")
Re: Factoring.... ("Jeffrey Walton")
Re: Factoring.... ("Tom St Denis")
Re: Data dependent arcfour via sbox feedback (Mok-Kong Shen)
Re: Breaking a DES encrypted code. (Richard Herring)
----------------------------------------------------------------------------
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Factoring....
Date: Wed, 4 Apr 2001 04:06:58 -0400
If factoring is only as hard as finding square roots of quadratic
residues in a modulo p system, then is complexity is determined by the
density of the non trivial square roots that are quadratic residues in
that modulo p system?
------------------------------
From: "Jack Lindso" <[EMAIL PROTECTED]>
Subject: Re: A group ?
Date: Wed, 4 Apr 2001 10:14:57 +0200
Well I wold like to know whether there are any specific guidelines by wich
you should test
a given F().
Cheers.
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Jack Lindso wrote:
> > Hey, to all I'm just starting to learn cryptology and i've gotten to the
> > need of
> > finding out :
> > if we know that F(P,K1)==>C1
> > and F(C1,K2)==>C2 {C1!=C2}
> > then can we find K3 such that F(P,K3)=C2
>
> So what do you want us to do? The answer is, it depends on F.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: efficient rabin signature?
Date: Wed, 04 Apr 2001 02:04:40 -0700
Tom St Denis wrote:
>
> Bryan Olson wrote:
> > Tom St Denis wrote:
> > [...]here is an idea I was just thinking of..
> >
> > I think a standard for verify-efficient Rabin signatures
> > (with appendix) is a good idea. There are some tricky
> > points.
> >
> > >The secret key is <p,q> which are two large primes (congruent to 3 mod 4)
> > >such that N=pq is a blum integer. To sign a message you perform the
> > >following.
> > >
> > >1. K = (hash of message) * 65536
> >
> > How did you choose 2^16?
>
> Well any size. The idea is that you increment the lsbs until you hit a good
> one.
That's clear. I'm asking why 16 bits. I think it's an
arguably reasonably choice; I'm just wondering if 8 bits would
be better, or something in between.
> > >2. if J(N, K) = 1 then solve for the principal square root of K
> >
> > Half the values k such that J(N, k) = 1 do not have a square
> > root mod N (where N is a Blum integer). Fortunately, since
> > the signer knows p and q, he can check both Legendre symbols
> > to determine whether it's a quadratic residue.
>
> I thougth the Jacobi and Legendre symbol were equivelant for odd N?
The Legendre symbol is only defined for (odd) prime N. The
Jacobi symbol generalizes it to odd composite N, but not in
the sense that it is the QR status. The Jacobi symbol of a
composite is the product of the Legendre symbol of each of
the (not necessarily distinct) prime factors.
> Isn't
> the jacobi used in the QS factoring to find good factor base primes? i.e
> J(N, Pi) != -1?
I don't know enough to say.
> > A conventional hash digest is too small. You must use a
> > full-domain hash or pad K. Padding for Rabin signatures
> > is tricky.
>
> Ah...well you could pre-append 1 bits so you get 111111111...etc || hash ||
> binary_counter. That way it won't have answers in Z ever.
It has to be less than the modulus of course. You could
start with one zero bit in the position of the leading 1 in
N. You probably also want to mark the boundary between the
padding and the digest.
Fixed padding for Rabin signatures is currently debatable.
The chosen message attacks have used attacker-chosen
content. Schemes using full-domain hashing have some
significant security results.
> > >3. If J(N, K) = -1 then increment the lower 16 bits of K and goto 2
> >
> > As noted above, you need to skip all the non-QR's.
> >
> > I don't think giving away the non-QR status of the rejected
> > K values where J(N, K) = 1 hurts, but can you prove it's
> > safe? If not, I suggest generating the candidates in a
> > key-dependant order, so the verifier couldn't tell what
> > numbers were rejected. (I wouldn't use a random order,
> > since that would produce multiple signatures for the same
> > message.)
>
> Well the bottom L bits could be made by BBS? I.e use the message hash as a
> seeking point into the BBS output then just output L bit words until the
> entire word is a QR?
Or a hash-based generator should be fine. The method need
not be specified since it doesn't effect the verifier.
> > >To verify you simply do
> > >1. K = M^2 mod N
> > >2. Divide K by 65536
> > >3. Compare K against the hash of the message.
> >
> > So for a typical message, there are about 16000 other
> > signatures that will verify.
>
> Why?
Oops, my mistake. That should be about 64K valid
signatures. The verifier ignores the bottom 16 bits of M^2
mod N. There are 64K possible contents in the low 16 bits,
and we expect one if four of these to be a QR. For each
that's a QR, all four square roots are verifiable signature
for the same message.
We need to balance the number of spurious valid signatures
against the chance that there's no signature for some
message we want to sign. That's my question of the 16-bit
field is about.
Note that Rabin-Williams has no such problem; each message
has a signature (as long as we don't hit a multiple of p or
q, which we won't). I guess the other 3 square roots would
also verify, but that's all. It's also nearly as fast to
verify, since the shifting and subtracting steps are linear
time, while the squaring is typically quadratic.
What I like about the verifier-ignored field approach is the
tiny verification code (with the possible exception of the
hash function).
--Bryan
------------------------------
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Clarification - Re: Factoring....
Date: Wed, 4 Apr 2001 05:28:19 -0400
Reply-To: "Jeffrey Walton" <[EMAIL PROTECTED]>
Sorry, I received a personal response to using 'modulo p'. Please allow
me repost:
After I posted, I saw the error. n = p*q. Finding the quadratic
residue would occur in modulo n.
If I recall, there are basically n/2 quadratic residues, and n/2 non
quadratic residues.
Also, in n = p*q, I don't want trivial quadratic residues. For example:
p = 3*5.
1^2 = 1 mod 15 and 14^2 = 1 mod 15. These are trivial. However, 4^2 = 1
mod 15 is not trivial. (Of course, understand = to be congruence).
So, what is the complexity of an algorithm that finds the square root of
a quadratic residue, after finding a non trivial quadratic residue.
My "gut instinct" tells me I will find a non trivial quadratic residue
quickly. I'm trying to define the hueristic "quickly".
"Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
news:9aekis$sji$[EMAIL PROTECTED]...
| If factoring is only as hard as finding square roots of quadratic |
residues in a modulo p system, then is complexity is determined by the
density of the non trivial square roots that are quadratic residues in
that modulo p system?
------------------------------
From: [EMAIL PROTECTED] (Stefek Zaba)
Subject: Re: How do I exchange the values of A and B
Date: 4 Apr 2001 09:14:32 GMT
In sci.crypt, Dave Moore [EMAIL PROTECTED]> (ROT13=) wrote:
> Back when Dinosaurs roamed the Earth and 64K was fully populated memory this
> was a classic.
> Assuming "A" and "B" contain integers, reverse their contents without using a
> 3rd storage location.
> A' = A xor B
> B' = B xor A' = B xor (A xor B) = A
> A''= A' xor B' = (A xor B) xor A = B
> Three instructions, and depending on the processor sometimes faster than using
> a 3rd location. But OBTUSE ! Doing this without comments was a capital
> offense.
And often coded as a C preprocessor macro. And giving rise to unexpected
consequences when A and B turn out to refer to the same storage location,
which promptly gets zero'd. Which makes for a nice toy example for formal
proof-of-correctness tools.
Stefek
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Factoring....
Date: Wed, 04 Apr 2001 09:41:57 GMT
"Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
news:9aekis$sji$[EMAIL PROTECTED]...
> If factoring is only as hard as finding square roots of quadratic
> residues in a modulo p system, then is complexity is determined by the
> density of the non trivial square roots that are quadratic residues in
> that modulo p system?
No you have that backwards. Finding square roots is as hard as factoring.
Factoring can be very easy if for example your number is B-Smooth :-)
Tom
------------------------------
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Re: Factoring....
Date: Wed, 4 Apr 2001 06:05:34 -0400
Reply-To: "Jeffrey Walton" <[EMAIL PROTECTED]>
Thank you Tom. I realize I'm somewhat backwards. Assume factoring is
is only as hard as finding the square root of a quadratic residues in
modulo n (n = p*q - got it right this time :). The supposition does
indeed seem to be backwards. This is by intent.
Does this mean factoring is NOT an np class problem? Further, does this
mean factoring is now a p class problem. I'm not inferring anything
about p = np (or they not equal), or the possible union of np and np
complete. I know there's an active debate about where factoring lies
(p, np, or np complete).
Next question: If it is true that factoring is as hard as finding a
square root of a quadratic residue modulo n, how hard is exponentiation
(or, what the cryptographist concern themselves with - the discrete log
problem).
That is, if I can factor (assuming because factoring is easy and
therefore most likely a p problem), can I find a discrete log easily?
And the reverse: If discrete log is easy, is factoring easy? I think
thie answer to this question is generally NO, but I might be mistaken.
Jeff
[EMAIL PROTECTED]
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:F%By6.17523$[EMAIL PROTECTED]...
|
| "Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
| news:9aekis$sji$[EMAIL PROTECTED]...
| > If factoring is only as hard as finding square roots of quadratic
| > residues in a modulo p system, then is complexity is determined by
the
| > density of the non trivial square roots that are quadratic residues
in
| > that modulo p system?
|
| No you have that backwards. Finding square roots is as hard as
factoring.
| Factoring can be very easy if for example your number is B-Smooth :-)
|
| Tom
|
|
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Factoring....
Date: Wed, 04 Apr 2001 10:16:52 GMT
"Jeffrey Walton" <[EMAIL PROTECTED]> wrote in message
news:9aerg8$hv0$[EMAIL PROTECTED]...
> Thank you Tom. I realize I'm somewhat backwards. Assume factoring is
> is only as hard as finding the square root of a quadratic residues in
> modulo n (n = p*q - got it right this time :). The supposition does
> indeed seem to be backwards. This is by intent.
>
> Does this mean factoring is NOT an np class problem? Further, does this
> mean factoring is now a p class problem. I'm not inferring anything
> about p = np (or they not equal), or the possible union of np and np
> complete. I know there's an active debate about where factoring lies
> (p, np, or np complete).
>
> Next question: If it is true that factoring is as hard as finding a
> square root of a quadratic residue modulo n, how hard is exponentiation
> (or, what the cryptographist concern themselves with - the discrete log
> problem).
If you can find the square root modulo a composite then you can factor. I
think this is because there will be four roots, x, -x, y and -y. If you
find a quad such that x != y by doing a square root then you can factor
since x^2 = y^2 and then gcd(x - y, pq) will be a divisor you want.
I think it's more appropriate to say "square roots are as hard as factoring"
not "factoring is as hard as the square roots". Since guessing square roots
is not the easiest way to factor.
> That is, if I can factor (assuming because factoring is easy and
> therefore most likely a p problem), can I find a discrete log easily?
>
> And the reverse: If discrete log is easy, is factoring easy? I think
> thie answer to this question is generally NO, but I might be mistaken.
The NFS and QS for that matter can be generalized to solve the Discrete Log
problem because they are remarkebly similar to the laymen like me. In
factoring you are finding the *sum* of prime powers, in discrete log you are
finding the *product* of prime powers. It's then easy to show that they are
about as hard. The discrete log differs in the last step the matrix
reduction since in factoring you have a GF(2) matrix. In discrete log your
matrix is in GF(p) which takes more memory and is slower.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Data dependent arcfour via sbox feedback
Date: Wed, 04 Apr 2001 13:14:20 +0200
Terry Ritter wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> >My worry stems on the one hand from your claims of general
> >coverage in previous posts and on the other hand from
> >a diagram on you web page, which in my view seems to cover a
> >quite general feedback scheme.
>
> Which diagram, on what page?
Right at the section on 'Dynamic Substitution' there is on
the left a diagram. The box labelled 'Changes Controller'
has an input from above. I understand that that input is
a quantity that results from the current processing state
(otherwise why 'dynamic' in the name of the scheme?).
Hence that's feedback control in the ordinary sense.
> >That's why I wanted to know
> >explicitly whether using feedback as such is or is not
> >violating your patent. Incidentally, feedback is a mechanism
> >that has interested me for some time. (A couple of my humble
> >crypto designs employ feedback.)
>
> Well, feedback has long been a very basic part of hardware circuit
> design (analog, or "linear" design). Most Op Amp (operational
> amplifier) circuits use extensive negative feedback, often to make the
> gain effectively independent of the active device, and to reduce
> distortion. Most oscillator circuits use some form of positive
> feedback to replace any loss in the frequency-selective section.
> There is also a concept of "feedforward," often used to cancel
> distortion without using feedback. Feedback is fairly old (70
> years?), very common stuff, and very often treated in the technical
> literature.
>
> With respect to cryptographic feedback, autokey stream ciphers are
> also quite old. The PK-Zip cipher (from a decade ago?) is a modern
> example. I don't think we can draw a useful feedback analogy to
> Dynamic Substitution per se, although the inverse process (the
> extractor) might be more like it. There is no intent in the Dynamic
> Substitution patent to control feedback per se.
>
> I cannot even imagine trying to get a general patent on feedback now,
> because it is a widely-understood part of technology; there is massive
> prior art. But even now, there might be particular ways to control or
> use feedback which might be patentable.
I can't exclude misunderstanding. But the 'dynamics'
in your scheme must in my view necessarily be derived
from the current (ongoing) processing state and hence goes
hand in hand with feedback. Otherwise the word 'dynamic'
in the name would be misleading.
> >Oh yes, it could certainly impose its laws onto foreign
> >countries and do the said 'prosecutions' through the help of
> >its mighty military forces. The day of the scenario you
> >described may in fact be nigh. Who knows the future for sure?
>
> I did not say "impose its law," I said "prosecute . . . in foreign
> countries"; that would be in their PTO, or the EPO. One problem for
> the US is that when inventors choose to only patent in the US, only US
> industry is controlled by the patent, which then may not be able to
> compete worldwide. It is hard to compete with companies who do not
> have to pay for the research which resulted in the product.
Patents apply only to the countries where these have
been submitted and granted and paid for (fees for the
patent offices). There is no free lunch. If you think
that protecting your invention in another country is
worthwhile from a business point of view, then it is
wise to spend some money to get a patent in that country.
It might be a good idea to have a single patent office
for the entire world. I am not sure. But that's totally
unrealistic before the United Nations succeed to unite
the nations in the real sense of the word.
> >On the other hand, in another post you seemed to claim that
> >generation of a very large table statically for later use
> >(through choice of columns analogoug to selection with key
> >in polyalphabetic substitution) would be considered as in
> >conflict with your patent, even though there is no dynamic
> >creation of table. This point is non-trivial as far as the
> >coverage goes and it is important to have a clarification of
> >that.
>
> There have been many points in the past few days. The best match for
> this that I recall was that if someone wanted to get around the
> Dynamic Substitution patent by saying they did not have "a
> substitution table" and then produced some sort of logic structure --
> one element at a time -- which in effect *was* a table, we should
> expect that to infringe as well. It is not that easy to get around a
> patent.
>
> I don't understand your point about "generation of a very large static
> table," since the Dynamic Substitution issue is not about size
> (although it must be small enough to be realized). The whole point of
> Dynamic Substitution is to re-arrange the contents of the table. That
> is not done in polyalphabetic substitution, which I believe I gave as
> prior art in the patent itself. In general, if the contents of the
> tahle are not re-arranged, it is not Dynamic Substitution.
What I meant is sort of this stuff: I construct a
polyalphabetic substitution table with a very large number
of columns (each being a permutation). I can address the
columns with a numerical key which is a function of the
output of a PRNG and some value obtained in the current
state of processing (e.g. the sum of the last plaintext
and ciphertext character being processed). Now, what I
understand as dynamic would be constructing at the very
moment of use (i.e. in the middle of encryption processing)
one or more new columns for substitution based on some
value obtained in the current state of processing. The
table I just described is static. It is not that
flexible/universal (hence perhaps performing less well
from crypto point of view) as the dynamic one, but comes
very near to it for the intended purposes, because fairly
randomly picking one substitution column from a huge number
of the statically determined ones provides almost the same
'randomness' (benefit) as creating a substitution column
dynamically (on the fly). Now allow me the explicit
question: Does such use of huge static substitution tables
violate your patent, where tables are dynamically generated/modified (if
I don't err) and, if yes, why?
> >I don't have problems with the purposes of the patent laws,
> >nor with copyright. I think that they both have merits in
> >principle. Inventors should be rewarded. What worries me is
> >the 'practice' of having very general claims in the patent
> >documents, which, even if these are actually largely
> >restricted by (eventually present) other clauses of the same
> >documents, may cause undesirable confusions to other
> >practioners or potential inventors, mistakingly thinking
> >that all what they intend to do falls already in the domain
> >of these general claims. That I think would be very bad.
>
> The only solution I can offer is the same one you have been
> essentially calling unfair, and that is to learn about patents,
> claims, and patent law. What other solution could there possibly be?
>
> Not everybody learns in school every skill they need in real life. I
> think technical people should know how to read a patent, and how to
> interpret claims, and thus exhibit less of a tizzy when they are
> confronted with such a monster. If someone considers patents
> important enough to potentially disturb their work, they may need
> patent skills just to do their work.
Even skilled people can err. Otherwise why do we have
patent lawyers and patent courts at all? What I was saying
is that patent documents should be clear-cut, exactly
restricted (as tightly as possible) in coverage to the
ideas that are really novel. These should never be 'coated'
in such general terms that they at least seem (even if not
intended so) to cover things that they shouldn't cover. Let
me give a 'hypothetical' analogy. Let's turn the clock back
and imagine that there are yet no automobiles. Someone
invents a car, driven by an engine. Clearly he deserves
very well a patent. That patent document should neatly
describe the invention as such, namely a vehicle with
wheels and so on and with a certain kind of engine and
other relevant technical details. But the patent shouldn't
lay any general claims about vehicles that serve to
transport persons and goods. For such a general formulation
could be interpreted to cover not only automobiles but also
coaches, boats, ships, airplanes and (in future) rockets.
If you look at the claim in your patent about combining
two streams to produce a more complex stream, I suppose
you'll understand what I mean here.
> >I am not sure whether the term nonlinear combiner couldn't be
> >'interpreted' to encompass e.g. modular multiplication of two
> >entities, use of F-functions of DES, rotation of one entity
> >with modular addition of another, and use of a nonlinear PRNG
> >to process a bit stream. These are however in my view all prior
> >art.
>
> All of which is fine with me. Dynamic Substition is the *name* of the
> patent; it does *not* imply that anything which is "dynamic" and which
> includes some form of "substitution" is covered.
>
> Dynamic Substitution is just shorthand for the claims. You seem to
> find this misleading for some reason, but the precise alternative
> would be to call it by the full claim description, and avoiding that
> horror is the reason we have names.
It is the 'generality' of the individual claims (of not
only your patent but also of plenty others) that actually
worries me. But certainly the title of you patent provides
some amount of relevant context. I think that it correctly
conveys the idea that the substitution is not predetermined
(fixed) but is dependent on the 'runtime'. Could you
also say something about the topic of nonlinear combiner?
My view is that, if you come up with a specific new type
of combiner that is entirely distinct from what one knows
in literature and you can show that it has specific
crypto-beneficial properties, then you deserve very well
a patent. But such a patent should not lay claims on
combiners that are nonlinear 'in general', for others
have invented some such before you and will invent
some after you that are distinct from your specific
combiner yet these are ALL nonlinear in nature. Have I
explained my point sufficiently understandably?
> >If something is completely new, it could hardly be 'general',
> >but, in contrary, singular/special/particular.
>
> That sounds odd to me. It is the new work which has little prior art,
> which thus imposes few limitations on a new patent.
My point is that a 'completely new' mechanism (or whatever)
has by definition little in common with existing ones.
Consequently it could not properly (and should not) be
formulated in such (general) terms that the existing
(commonly known) entities are also covered. See also above.
> >I don't have any personal plans to earn money in any field.
> >There is hence no personal 'problem' for me at all. Others
> >have raised though the point that the good intended purposes
> >of patent laws would be undermined, if the practice of granting
> >patents is improper, allowing persons to get patents without
> >actual novelty or with much more coverage than the underlying
> >ideas deserve. I guess that many people in this group have
> >a common (and unfavourable) opinion about e.g. Hitachi's
> >rotation patents.
>
> I have long thought you were making far too much of the Hitachi
> claims. Haven't there been several messages on sci.crypt, each with a
> pretty good technical analysis, which told you that this was not the
> problem you claimed? Did you not read those? Did you forget them?
> How many times must you be told before you will accept reality? From
> what dark recesses does this strange fear continue to re-emerge and
> infest all the newbies with this baseless dark foreboding?
Sorry. I didn't notice any good technical analysis of
the Hitachi patent in the group. All I learned is the
fact that the rotation does not use an amount of rotation
that is static (fixed) but dynamic (variable). What
essentially more did you read out from the posts?
M. K. Shen
===========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Breaking a DES encrypted code.
Date: 4 Apr 2001 11:18:33 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Mok-Kong Shen ([EMAIL PROTECTED])
wrote:
> William Hugh Murray wrote:
> >
> > Well, it is certainly being used for SETI. Has been used for brute force
> > attacks against DES challenges. In order to paricipate, one need only click
> > on an icon or two. It is almost that simple.
> Yes. There are also universities where the computers of
> the campus are connected to do distributed computing.
> My impression is, though, that most commercial firms
> (probably with the exception of very large ones, I don't
> know) seem to opt to neglect that potential, which is
> wasting of resources in my view. I am not sure whether
> this is because of availability/popularity of good
> software needed for distributed computing or of other
> factors.
Fear of trojans, I think. Who knows what sensitive information
a distributed client might send back to the server?
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
** 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
******************************
