Cryptography-Digest Digest #819, Volume #9 Fri, 2 Jul 99 01:13:07 EDT
Contents:
Re: Quantum Computers ([EMAIL PROTECTED])
Re: new book (Stefan Katzenbeisser)
Re: How do you make RSA symmetrical? ([EMAIL PROTECTED])
Re: Quantum Computers ("Douglas A. Gwyn")
Re: Quantum Computers (David A Molnar)
Re: The One-Time Pad Paradox ("Douglas A. Gwyn")
Re: Quantum Computers ("Douglas A. Gwyn")
Re: MP3 Piracy Prevention is Impossible ("Douglas A. Gwyn")
Re: trapdoor one way functions (Nicol So)
Re: How do you make RSA symmetrical? (David A Molnar)
Re: additive RNGs ("Douglas A. Gwyn")
Re: Can Anyone Help Me Crack A Simple Code? (mercury)
Re: Quantum Computers (Anti-SpamNameHere)
Encrypted Boot Sector (Zachary)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computers
Date: Fri, 02 Jul 1999 01:02:35 GMT
In article <7lfric$i48$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) wrote:
> If one starts with that assumption and I think it is a good
assumption that
> the NSA has quantum computers and most likely has had them for many
> years. If one makes this assumption then the idea behind future
encryption
> system should be to make the entropy such that for an average english
text
> message one sends or encrypts. There should exist the possiblitlity
of more
> than one soultion. This would prevent a break since there would not
be a
> unique decryption to a given message. The problem with short key
methods
> like all the AES candidates is that for any resonable length message
the
> key is so short that there exists only one unique decription to a
english
> message and this is where the so called experts want the masses to
use.
> Try scott19u.zip its better.
That's a laugh. Why haven't you answered my earlier post 'Dave Scott,
I have some questions' (or something like that, just do a search of
about two weeks ago...).
You keep boasting but never prove anything. Your a laugh. Can you
search a 256 bit key (which all AES ciphers support) before you get
bored? I don't think so. Can anyone of us do that during a lifetime?
I think not.
Even SAFER+ with it's weakness (in 256 bit keys there is a break of O
(2^200)) can't be searched anytime soon.
Answer my previous post (I can find it if you want). I have some
constructive (and I mean it) questions.
(BTW how do you make the large random keys? You never answered that
one either...)
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: Stefan Katzenbeisser <[EMAIL PROTECTED]>
Subject: Re: new book
Date: Thu, 01 Jul 1999 10:22:21 +0200
John Savard wrote:
>
> He's just giving us an early mention of the book, and asking if anyone
> knows any more. And, since Kirkus Reviews does have the general reader
> in mind, it is not elitist to hope that an assessment of "too
> technical" may be an indication of real content. (Of course, the
> possibility of it indicating poor presentation isn't eliminated either
> until one actually sees the book.)
I read the German edition of this book; it is a curious fact
that the German edition does not mention "code breaking" in
the title, it just refers to cryptographic techniques.
I think the book is quite a good introduction to a reader
who has no knowledge of cryptography at all and is not really
interested in the mathematical foundations of cryptography.
I can only disagree with the opinion of the reviewer that the
book is too technical; it is not, so most people on this list
perhaps won't like it. Anyway, for the intended audience the
book might be really interesting.
Regards,
S.K.
--
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
| Stefan Katzenbeisser
| e-mail: [EMAIL PROTECTED]
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How do you make RSA symmetrical?
Date: Fri, 02 Jul 1999 00:58:26 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Gilad Maayan) wrote:
> Okay, I get it. The question is, how does this affect processing time?
> The main reason I'm asking "which hammer to crush my testicles with",
> as someone put it, is that my specific application is hampered by
> severe hardware restrictions. I'm using a processor that can barely
> compute M^e, where M is 20 bits. Naturally, even the slightest
> increase in plaintext size enormously increases the number of
> mathematical operations required. Now, if you encrypted your message,
> padded with all zeroes, would my pathetically slow microprocessor be
> doing 20 bits^n, or 768bits^n? Also, would you have to physically add
> the zeroes, or could you simply exponentiate, say, "93751"?
>
Well it's not that simple because the simplest exponent algoritm (is
mentioned in the RSA paper) is the squaring and multiplying method.
This means you take 'e' your exponent and make it into a n bit string
(n = size). You then go thru the array like so
R = 1
for i = 1 to n
if E[n] then
R = R * M
else
R = R * R
next i
Where R is the output and M is the input (msg). This is linear time
with respect to the exponent size in bits (not the actual value). So
you will have to perform many mult's if you have a large exponent. I
would concentrate on optimizing your multiplication code though (which
is also linear time with respect to the size in bits...).
Using small inputs does not guarantee fast multiplications (if you are
using a fast out method)...
I would not suggest RSA or any 'big' number algorithm if you are
seriously hampered for time or hardware space. Typically I would
imagine RSA (1024 bit) taking about 20 to 40 seconds for one op
(assuming a crystal of about 8Mhz).
Tom
--
PGP key is at:
'http://mypage.goplay.com/tomstdenis/key.pgp'.
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Fri, 02 Jul 1999 03:30:49 GMT
David A Molnar wrote:
> I find it pretty heavy going, but then again I'm
> learning the quatum physics as I go along.
I recommend Dirac's "Principles of Quantum Mechanics" (4th Ed.),
which I found far better at getting to the heart of things than
the official textbook back when I took QM.
One point that has been appreciated only relatively recently is
that the Copenhagen notion of the collapse of the physical wave
function is bunk -- it is more productive and less paradoxical
to consider the "entanglement" of the state of the observer with
the state of the observed. There are papers about this on the
net, although I forget where. Fortunately, Dirac notation fits
in very well with this new approach.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: 2 Jul 1999 03:44:30 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> I recommend Dirac's "Principles of Quantum Mechanics" (4th Ed.),
> which I found far better at getting to the heart of things than
> the official textbook back when I took QM.
Thanks. I have a bit of time this summer and will see if
I can find it. Although I confess to disliking the
bra-ket notation, which I understand Dirac as having
invented. Vectors should be vertical.
> One point that has been appreciated only relatively recently is
> that the Copenhagen notion of the collapse of the physical wave
> function is bunk -- it is more productive and less paradoxical
> to consider the "entanglement" of the state of the observer with
> the state of the observed. There are papers about this on the
> net, although I forget where. Fortunately, Dirac notation fits
> in very well with this new approach.
You know, this would go a very long way towards explaining
why none of the papers I found mentioned "collapse." Also
explains part of why I couldn't get the two ideas to
reconcile. I'll look for the papers.
Thanks,
-David Molnar
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: The One-Time Pad Paradox
Date: Fri, 02 Jul 1999 03:41:57 GMT
"Robert C. Paulsen, Jr." wrote:
> Maybe your point but not mine.
Maybe you should try harder to understand his point.
He was trying to show you why yours (Savard's) is bogus.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
Date: Fri, 02 Jul 1999 03:19:19 GMT
Greg Ofiesh wrote:
> In the public sector?
In the human community.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: MP3 Piracy Prevention is Impossible
Date: Fri, 02 Jul 1999 04:10:43 GMT
Gilles Fayad wrote:
> Anyone with good pointers on watermarking techniques?
You should be able to find several sites via a Web search for
"digital watermark" and/or "steganography". This subject has
seen a lot of research and development during the past few years.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: trapdoor one way functions
Date: Fri, 02 Jul 1999 00:07:41 -0400
[EMAIL PROTECTED] wrote:
>
> Nicol So wrote:
>
> > No. We don't know if one-way functions exist because... we simply
> > don't. Knowing whether one-way functions exist, either in the
> > affirmative or in the negative, would settle the P =? NP question, and
> > it would be such a big news that even people who are only casually
> > interested in the computer science would notice.
>
> I don't think that's entirely right. Obviously if one-way
> functions exist, then P!=NP. I don't think anyone has shown
> that the non-existance of one-way functions would imply P=NP.
> Thus knowing wether one-way functions exist is not known to
> settle P ?= NP.
I arrived at that conclusion based on a simple argument. I have to
admit that I didn't check the argument as carefully as I could. I think
the argument is logically valid, but if there are any problems, they are
in the formalization of the concepts.
Here's an *outline* of the argument. See if you can spot anything
wrong.
First, some notations:
Let f be a mapping, say, from integers to integers. We use f' to denote
the function s.t.
f'(y) = x, where f(x) = y, if such an x exists;
= "no" (a special value not among the integers) otherwise
Let L be a language. We denote by verify[L] a function s.t.
verify[L](x,c) = (x,"yes") if c is a "certificate" of x's
membership in L
= (x,"no") otherwise
The concept of "certificate" here is as in the definition of NP. (All x
in L have certificate(s). No non-member of L does. Certificates must not
be "too long").
Proposition 1:
"f is weakly one-way" <=> (f in P) and not (f' in P)
Proposition 2:
"L in NP" <=> (verify[L] in P)
(Note: slight abuse of notation)
The argument: If (weak) one-way functions don't exist, for any language
L in NP, for any verify[L] function in P, verify[L]' is also in P.
(verify[L]' is essentially the search problem for certificate of
membership in L).
Nicol
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: How do you make RSA symmetrical?
Date: 2 Jul 1999 03:06:19 GMT
[EMAIL PROTECTED] wrote:
> Well it's not that simple because the simplest exponent algoritm (is
> mentioned in the RSA paper) is the squaring and multiplying method.
> This means you take 'e' your exponent and make it into a n bit string
> (n = size). You then go thru the array like so
> R = 1
> for i = 1 to n
> if E[n] then
> R = R * M
> else
> R = R * R
> next i
> Where R is the output and M is the input (msg). This is linear time
> with respect to the exponent size in bits (not the actual value). So
Note that here your unit is a multiplication. That is, you're
doing O(n) multiplications.
> you will have to perform many mult's if you have a large exponent. I
> would concentrate on optimizing your multiplication code though (which
> is also linear time with respect to the size in bits...).
^^^^^^^^^^^^^^^^
Here your unit for talking about "linear time" is different.
Else 1 multiplication would be 1 unit, therefore constant time.
So if multiplication is O(n) "more primitive" bit operations
and you do O(n) multiplications, your algorithm is
O(n^2) of these primitive bit operations.
I'm pointing this out because otherwise it reads like
exponentiation and multiplication take the same time,
which they don't.
The thing is, your multiplication of R * R or R * M is
quadratic for naive multiplication, goes to O(n log n)
for very large n using a discrete fourier transform,
and only becomes O(n) under some conditions which
I can't remember right now but are in Knuth's
_The Art of Computer Programming_ .
You also need to take R mod n at each step, or
else your R will become too big and unwieldy
to handle. This ensures further that for
s = ln n = "size of the modulus", you only
have to deal with numbers of size 2s at most.
Modular exponentiation should take about O(n^3)
bit operations, assuming a O(n^2) multiplication
algorithm. You're still right in noticing that
the mults are where the possibility for
improvement lies, though.
-David Molnar
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: additive RNGs
Date: Fri, 02 Jul 1999 04:07:53 GMT
[EMAIL PROTECTED] wrote:
> I decided to play with Additive RNGs today (fionaci type).
Fibonacci, the famous rabbit breeder :-)
> 1. What is the quickest way to do the shift? I.e S[0] = S[1].
> S[1] = S[2]. I am using a memcpy ...
If you're storing one bit per byte, which is the easiest way to
program such algorithms in C, this is almost the right approach.
However, you should use memmove(), not memcpy(), because the
latter can malfunction when the source and destination overlap.
Another method is to pack bits into unsigned integer types, in
which case the << and >> shift operators are generally fastest.
Since C doesn't provide direct access to the "carry bit", you
need to save it before shifting, e.g.
c = r % 1; // old low bit will be the "carry bit"
r >>= 1; // shifts r to the right one position
> 2. What is the cycle length for various array sizes.
It depends on the feedback function. Golomb's book "Shift
Register Sequences" (available from Aegean Park Press) is a
good introduction to this subject.
> 3. Are all LFSR polynomials good for this type of RNG?
No, for maximal period the characteristic polynomial must be
irreducible, and unless 2^n-1 (n = # stages) is prime, not
all irreducible polynomials yield maximal period. This is
covered in Golomb section 3.4.
> 4. The additive generator is linear? Is it at least statistical
> sound?
Whatever that means. Golomb discusses the "randomness" properties.
He also has a lot about nonlinear feedback shift registers.
------------------------------
From: mercury <[EMAIL PROTECTED]>
Subject: Re: Can Anyone Help Me Crack A Simple Code?
Date: Fri, 02 Jul 1999 00:09:25 -0400
Reply-To: [EMAIL PROTECTED]
Ed Yang wrote:
> Please give us some more information:
>
> Did you get those numbers from some person you know?
> Can you ask that person some questions for us?
> Did you get those numbers from your computer?
My "Black Box" description is quite accurate. I have a pice ofhardware
with a keypad. I can not find a way to interface it
to a computer and test for all possible keys.
The Black Box extrapolates a light code and a
date code from the ten digit number. If it
succeeds in doing this, it checks to see if
the date code has not expired according to its
internal clock.
Although I don't know what the output looks like,
I do know the black box understands it as a
light/date code.
I can get handfulls of ten digit codes that will
work for various light/date codes, but I will never
be able to get all of them for any specific light/
date combination.
The six codes I posted are all excepted as the
same light color. The dates are all the same -
DEC 1999. The box does not seem to be able
to distinguish between them - the same result for
all.
> When you get proposed answers from cryptanalysts, how will you
> verify that the answer is correct?
I can test any code by typing it into the kepad andget the response.
> Is it a pencil and paper algorithm?
I have been told that the algorithm is expected tobe broken eventually.
It won't matter when the
next line of boxes comes out - who cares if someone
has done this to old technology? The code is there
as a way to get extra money from "happy" customers.
If a customer is unhappy, the sales staff won't think twice
about offering free codes to them. This system is
not designed for high security. It is only designed
to keep casual users away.
The codes themselves are probably verified on a
microprocessor chip which is primarily there to do
something else entirely.
> Can you input 0000000000 to the algorithm and tell us the output?
I can try any number, just not in volume. Ican probably tell you that
the reply will be
"That's not a valid code" This would be the typical
response from most any randomly chosen number.
> Can you get any output for any input?
If the code is bad, it tells me its bad.
If the code is readable as a light color and date code,
I can get the light/date codes it sees.
> Do you have any friends who could communicate with us cryptanalysts
> who is willing to cooperate in your quest?
Not anyone who could put up with the flamming and notturn the
conversation into a flame war.
> After someone solves your problem will you announce that success?
>
Absolutely. I am here to learn and exchange information.I will develop
knowlege based on help I got from this
newsgroup and not share it.
However, I can not reviel what the Black Box is. I do not
want to hurt the Black Box company's business.
[EMAIL PROTECTED] Wrote:
> 3. Try to add small constants to some digits so
> that it will not change the sum of digits mod 10.
Would you mind giving an example of what a
successful result would be with numbers? This
sounds interesting, but I can interpret your statement
as having more than one possible meaning.
You have some very good points and I regret not being
able to discuss all of them tonight - running short
on time. I will definately reply tomorrow.
Dr. mike Wrote:
>Once you reverse engineer the electronics, the crypto
>will be easy. How much is it costing to reverse engineer
>this black box versus the cost of just buying new codes?
Some people are interested in studying
the the major "unbreakable" codes, some are interested
in the political issues of cryptography, some are interested
in the history of codes during war ... I'm interested in
learning how to break "simple" codes and what makes
a weak algorithm weak. This is not a money issue.
It costs me nothing to get codes, but I can not get large
amounts of them. It costs me nothing to try codes out if
I think I am on to something. It will cost me plenty if I
break a Black Box trying to solder wires under the key pad.
(I have not completely ruled this option out, but I would
rather avoid it if possible)
Douglas A. Gwyn Wrote:
>Then, with probability 0.99999999, the following function
>mimics your black box:
> f(x) = 0
>That's actually very good recovery, by cryptanalytic standards.
I have a box which accepts a small number of inputs as
"correct", and the rest are "wrong".
Your answer is to assume all inputs are wrong because
there are more "wrong" solutions than "correct" (????)
If there was a significant point here, I'm afraid I missed
it entirely.
The number of possible codes is ten billion.
Bill gates is worth over 80 billion dollars.
A high end desktop computer might run at half
a billion clock cycles per second, and hold over
15 billion bytes.
10 billion is a number which we see every day.
Yes, it is big in some aspects, but it is not
a big number in cryptography.
There is no reason to write a bunch of figures in
percentage format to make it look more
difficult than it is.
I've written a couple of programs to test for
similarities in these numbers. My programs usually
check all possibilities in a few seconds. It takes me
longer to make up dummy numbers designed to be caught
by the program (for testing purposes) than it does to
check all 100.0000000 percent of the possible
numbers.
------------------------------
Date: Thu, 01 Jul 1999 21:49:41 -0700
From: Anti-SpamNameHere <[EMAIL PROTECTED]>
Subject: Re: Quantum Computers
David A Molnar wrote:
>
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>
> > I recommend Dirac's "Principles of Quantum Mechanics" (4th Ed.),
> > which I found far better at getting to the heart of things than
> > the official textbook back when I took QM.
>
> Thanks. I have a bit of time this summer and will see if
> I can find it. Although I confess to disliking the
> bra-ket notation, which I understand Dirac as having
> invented. Vectors should be vertical.
>
> > One point that has been appreciated only relatively recently is
> > that the Copenhagen notion of the collapse of the physical wave
> > function is bunk -- it is more productive and less paradoxical
> > to consider the "entanglement" of the state of the observer with
> > the state of the observed. There are papers about this on the
> > net, although I forget where. Fortunately, Dirac notation fits
> > in very well with this new approach.
>
> You know, this would go a very long way towards explaining
> why none of the papers I found mentioned "collapse." Also
> explains part of why I couldn't get the two ideas to
> reconcile. I'll look for the papers.
>
> Thanks,
> -David Molnar
I highly recommend "Explorations in Quantum Computing" by Colin P.
Williams and Scott H. Clearwater. This is a most excellent introduction
to QC. Contents include:
Quantum Mechanics and Computers
Simulating a Simple Quantum Computer
The Effects of Imperfections
Breaking Unbreakable Codes
True Randomness
Quantum Cryptography
Quantum Teleportation ( - great for key distibution -)
Quantum Error Correction
How to Make a Quantum Computer
Published in 1997 by Telos (part of Springer Verlag) it includes a
CD-ROM with Mathematica models of different QCs.
[EMAIL PROTECTED]
------------------------------
Date: Thu, 01 Jul 1999 22:18:41 -0700
From: Zachary <[EMAIL PROTECTED]>
Subject: Encrypted Boot Sector
Hi,
I have a encrypted boot sector. And then I have the same boot sector
but its not encrypted. Is there anyway to find out logarithm that was
used to encrypted it. I know that it is in base 64. If that helps
you. Are there any programs that can find the logarithm? Any
inforamation on decryption would be helpful.
Zachary
------------------------------
** 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
******************************
