Cryptography-Digest Digest #964, Volume #10 Mon, 24 Jan 00 06:13:01 EST
Contents:
Re: Weierstrass Normal Form (John Savard)
Re: MIRDEK: more fun with playing cards. ("r.e.s.")
Re: What about the Satanic Seven??? (Terje Elde)
Re: What about the Satanic Seven??? (Terje Elde)
Re: MIRDEK: more fun with playing cards. (Paul Rubin)
Re: Calculating A^-1 Mod P ("ink")
Is Cramer-Shoup 98 with 5020 bits secure? (Oliver Moeller)
Re: Intel 810 chipset Random Number Generator (Vernon Schryver)
Help!!!Looking for Volunteers for my Masters Degree Research (paul mckee)
Re: Challenge. (Paul Schlyter)
Re: Java's RSA implimentation (Paul Schlyter)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Weierstrass Normal Form
Date: Mon, 24 Jan 2000 06:52:59 GMT
On Sun, 23 Jan 2000 17:09:20 -0800, Laura Feinstein
<[EMAIL PROTECTED]> wrote, in part:
>Given a cubic of the form u^3 +v^3 = a, where a is a rational number, how
>does one determine new coordinates, x and y given in terms of u and v by
>rational functions?
>I know the value of these functions:
>x=12*a/(u + v)
>y=36*a*(u - v)/(u + v)
>I'm looking for an algebraic method for determining these functions.
Unless the title of your post gives some clue that I'm missing, it's
hard to see what your question is. Given u^3 + v^3 = a, one knows
nothing about x and y or their relationship to u and v; thus, the two
rational functions that you've given can't be determined by algebra.
If you want to find u and v as functions of x and y, that would be a
straightforwards problem in algebra.
If
x = 12a/(u+v), then u+v = 12a/x.
If
y = 36a((u-v)/(u+v)), then, first we substitute for u+v, to get
y = 36a((u-v)/(12a/x)).
This lets us find that u-v = y(12a/x)/36a = y/3x.
Knowing u+v and u-v, it's easy enough to find u and v.
u = (( 12a/x ) + ( y/3x )) / 2
and
v = (( 12a/x ) - ( y/3x )) / 2
but I doubt that anything so simple was really your question.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: MIRDEK: more fun with playing cards.
Date: Sun, 23 Jan 2000 23:36:51 -0800
"Paul Rubin" <[EMAIL PROTECTED]> wrote ...
: r.e.s. <[EMAIL PROTECTED]> wrote:
: > K A 2 ... J Q
: > 0 1 2 ... 11 12
: > -----------------------------
: >Diamonds 0| 0 1 2 ... 11 12
: >Spades 1| 13 14 15 ... 24 25
: >Hearts 2| 26 27 28 ... 37 38
: >Clubs 3| 39 40 41 ... 50 51
: >
: >Take the "value" of a card as a *pair* of numbers (suit, facevalue),
: >i.e. the (row,col) coordinates in the above table, and leave it at
: >that while navigating the card layout. Don't waste time finding the
: >values 0-51!
:
: Actually it doesn't much matter what order the "card table" is
: in, if you have a convenient way to do the arithmetic. So try
: it like this:
:
: 0 40 28 16 4 44 32 20 8 48 36 24
: 13 1 41 29 17 5 45 33 21 9 49 37
: 26 14 2 42 30 18 6 46 34 22 10 50
: 39 27 15 3 43 31 19 7 47 35 23 11
:
: instead of in 0,1,2... order. Notice that with this layout,
: table[row, col] % 13 = col, and
: table[row, col] % 4 = row.
:
: You don't have to write down the above array or pay any attention
: to it at all; I just included it to help explain the principle here.
The table I gave is intended to be a visual indicator of several
things at once: the axes (absent in your table) are to remind
what the suit- and facevalue-associations are, while its interior
is to indicate the directions in which one navigates through it.
Pedestrian, I know, but some people really benefit from visuals
like that.
: >The real savings come in the final steps:
: >
: >While swapping the two cards, separately add up their "rows" & "cols".
: >"rows" is the mod 4 sum of their suits, and "cols" is the facevalue
: >sum (if it exceeds 0-12, increase the row sum by 1, and take
: >"cols" = facevalue - 13).
:
: Now just take the facevalue and suit sums mod 13 and 4 respectively,
: independently of each other. If the facevalue sum exceeds 13 just
: subtract 13. You don't have to adjust the row sum. This saves you
: a step. The Chinese Remainder Theorem in action ;-).
I don't think that's correct. Consider DiamondNine+SpadeNine:
That's (0,9)+(1,9)=(1,18)=(2,5), not (1,5).
Or the long way, (0*13+9)+(1*13+9)=31 =/= 1*13+5.
Have I misunderstood your meaning?
: >For the final step, put your finger at the (0,0) position in the
: >card-layout and move it the number of rows and columns indicated
: >by the (rows,cols) just obtained. You'll then be pointing at the
: >output card.
:
: Is this the scheme you were getting 3-4 characters/minute with?
: Or is it faster now?
Yup, that's been my method. Despite my early report of ~5 chars/min,
such a rate hasn't proved sustainable -- too much prolonged effort
is required -- and 3.5-4 chars/min, while sustainable, would be
demanding. 3+ chars/min is definitely sustainable for long periods.
: One final speedup: use all 52 values codebook style:
: 0=a, 1=b, ..., 26=z
: 27 = "escape" (like in ascii)
: 28 = unescape
: escaped, 0-9 = digits 0-9
: 1-2-3-27-1-2-3-4-5-28-6-7 would be read abc12345fg
I believe only one "escape toggle" is needed, and was thinking about
something like a-zA-Z, with UCletter=LCletter+26, and with X or Z
reserved as the "alphanumeric toggle". E.g. "33-8-49-0-0-7-49-1-24-4-51"
would read "Hi007bye."
: Now use other codes for frequently used phrases in your traffic.
: So if you're organizing a chocolate heist, you might use
:
: 29 = "president", 30 = "terrorist", 31 = "duct tape", 32 =
"helicopter",
: plus escape codes:
: escape-15 = "roadblock" escape-16 = "chocolate" etc.
If you did that, you'd probably want yet another "number-mode" toggle,
this one to distinguish between numbers meant as codes instead of
numbers meant as numbers. (The first one was for numbers meant as
numbers instead of numbers meant as ciphertext.)
: This cuts down the number of characters you need to send.
: It does mean your agents now have to memorize the codebook, or
: carry a printed copy (use edible paper like in the movies, or
: print on silk like in "Between Silk & Cyanide").
------------------------------
From: [EMAIL PROTECTED] (Terje Elde)
Subject: Re: What about the Satanic Seven???
Date: Mon, 24 Jan 2000 07:45:46 GMT
In article <[EMAIL PROTECTED]>, Sisson wrote:
>i think the PGP site makes you "i agree" to some agreement before you
>download. it also then has Q&A "Will you export it?" and if you answer the
>wrong question then it stops your download. It also checks your IP i think,
>to find what nation you're downlaoding from.
I'm in the process of setting up a server, and I could easily make a
script that people could run from my server to get the information about
the downloaders.
You connect to some site with crypto, the crypto site links to the scrip
on my site, the user fills out the info, and get his IP checked, and I
email that info to the admin of the crypto site, and link the user back to
where the file really is.
The server would be in Norway tho... Anyone know if that would be enough
for the crypto site to be able to export?
Also, anyone have the IP to country mappings? I could always go digg at
ripe, but I have no idea how to get dumps of an entire country.
>I think its a stupid law, because all you need i one person to email it
>country thats not allowed it, and its into distribution. they can't do
>simple checks like metal scans for terrorists that go to aeroplanes
We all think it's a stupid law.
Terje Elde
--
Hi! I'm a .signature virus! Copy me into your ~/.signature to help me
spread!
------------------------------
From: [EMAIL PROTECTED] (Terje Elde)
Subject: Re: What about the Satanic Seven???
Date: Mon, 24 Jan 2000 07:45:47 GMT
In article <[EMAIL PROTECTED]>, John E. Kuslich wrote:
>Is it not obvious to anyone with a brain (or even perhaps the people who
>write these regs) that people in the seven dirty nations can get
>whatever they want by well known means if it is otherwise available on
>the Internet?
>
>What am I missing here? The emperor really has no clothes, right???
If you consider only software, then yeah, the emperor is quite nude,
however I sustect the regulations are they way they are so that the US
government can crack down on people exporting military grade crypto
hardware to those countries.
It's all or nothing, so this is the way it has to be if they want to be
able to do that.
Terje Elde
--
Hi! I'm a .signature virus! Copy me into your ~/.signature to help me
spread!
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: MIRDEK: more fun with playing cards.
Date: 24 Jan 2000 08:20:11 GMT
r.e.s. <[EMAIL PROTECTED]> wrote:
>: Actually it doesn't much matter what order the "card table" is
>: in, if you have a convenient way to do the arithmetic. So try
>: it like this:
>:
>: 0 40 28 16 4 44 32 20 8 48 36 24
>: 13 1 41 29 17 5 45 33 21 9 49 37
>: 26 14 2 42 30 18 6 46 34 22 10 50
>: 39 27 15 3 43 31 19 7 47 35 23 11
>:
>: Now just take the facevalue and suit sums mod 13 and 4 respectively,
>: independently of each other. If the facevalue sum exceeds 13 just
>: subtract 13. You don't have to adjust the row sum. This saves you
>: a step. The Chinese Remainder Theorem in action ;-).
>
>I don't think that's correct. Consider DiamondNine+SpadeNine:
>That's (0,9)+(1,9)=(1,18)=(2,5), not (1,5).
>Or the long way, (0*13+9)+(1*13+9)=31 =/= 1*13+5.
>Have I misunderstood your meaning?
(0,9) + (1,9) = (1, 5) is correct.
The long way: (0, 9) = 48 (found at location 0,9 in the grid)
(1,9) = 9 (found at location 1,9)
48 + 9 (mod 52) = 5
which as expected is found at location 1,5 in the grid.
You can think of this as permuting the input letters so you no
longer have A=1, B=2, etc. but since you're using OFB mode,
you don't have to pay attention to this permutation.
>: Is this the scheme you were getting 3-4 characters/minute with?
>: Or is it faster now?
>
>Yup, that's been my method. Despite my early report of ~5 chars/min,
>such a rate hasn't proved sustainable -- too much prolonged effort
>is required -- and 3.5-4 chars/min, while sustainable, would be
>demanding. 3+ chars/min is definitely sustainable for long periods.
Hmmm, I'd hoped you could get it going faster. With some practice,
you can probably pound it out like a Las Vegas blackjack dealer :-).
I'll try to get a deck of cards and see how it goes.
------------------------------
From: "ink" <[EMAIL PROTECTED]>
Subject: Re: Calculating A^-1 Mod P
Date: Mon, 24 Jan 2000 10:33:47 +0100
Michael Scott schrieb in Nachricht ...
>
>"Kent Briggs" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Michael Scott wrote:
>>
>> > An alternative to the Euclidean algorithm.......
>> > Mike Scott
>>
>> I think you meant to say Euler, not Euclid.
>>
>
>No, I meant Euclid. Who lived in Alexandria, Egypt, as did Archimedes and
>Eratothenes amongst others, as I just found out on an interesting BBC
>documentary.
>
>Euler was German (I think)
>
>Mike Scott
He was Swiss. Sorry ;-)
K. In Albon
------------------------------
From: Oliver Moeller <[EMAIL PROTECTED]>
Subject: Is Cramer-Shoup 98 with 5020 bits secure?
Date: 24 Jan 2000 10:54:25 +0100
Path: news.daimi.au.dk!not-for-mail
Lines: 72
Message-ID: <[EMAIL PROTECTED]>
NNTP-Posting-Host: harald.daimi.au.dk
X-Trace: xinwen.daimi.au.dk 948479495 10542842 255.255.255.255 (21 Jan 2000 18:31:35
GMT)
X-Complaints-To: [EMAIL PROTECTED]
NNTP-Posting-Date: 21 Jan 2000 18:31:35 GMT
X-Newsreader: Gnus v5.7/Emacs 20.5
Xref: news.daimi.au.dk sci.crypt:133457
[[reposted]
Hi everyone,
Maybe it is not custom to place a 'bet' in this newsgroup, but I nevertheless
will (see http://www.brics.dk/~omoeller/sub/challenge.html ).
In Crypto'98, Cramer and Shoup presented a public key crypto system, that is
not compromised by adaptive chosen cipher-text attack. This means, even if an
evesdropper can decrypt arbitrary messages M' =/= M, it does not help him to
decrypt M.
I was wondering how tedious it would be to implement it and whether it would
be very slow - to my surprise, it is not too bad in both respects. But I had
to diverge from original suggestions, like:
When generating the key, generators of the prime modulus p have to be
found; my way to do that is to chose p in a way, that all prime factors
(q_1...q_n) of p-1 are known. Then by Fermat, for g in {2,...,p-1}
g is a generator of p iff (for all i) g^((p-1)/q_i) =/= 1 (mod p)
Then generators can be generated by picking random numbers and checking for
that property.
(This is a generalisation of the method suggested in [CS98], 5.1)
Key generation seems to be very tedious. It took about 3 weeks on a 130MHz PC
to generate a key with a 5020bit prime modulus. The slow part was to find a
prime p, where the factorization of p-1 is known and contains one big prime.
For this key, it takes about 120 minutes [heavily dependent on architecture]
to en/decrypt with a Java implementation, so it is not of 'industrial
interest', but feasible, if small amounts of data are to be sent
sparsely. Moreover, you can do it with a web browser without installing any
software.
This is the largest key I was able to generate. I did not carefully estimate
what kind of (standard) machinery it would take to break this with known
discrete log algorithms, but it should be beyond hopes with brute force
algorithms.
Is there a leak that compromises security?
In fact, the used key has a _special_ property that might be the
known-ciphertext attack easier: In, p-1 one of the small prime factors occurs
twice. Possibly, this could be exploited.
But my bet is, that this does not help.
In fact, I'm offering a prize of 1000,- Danish Kroner (admittedly not a
fortune, about 140 US-$) for the one, who would manage to retrieve the
original message text, given the cypher text and my public key:
http://www.brics.dk/~omoeller/sub/challenge.html
I strongly believe, that this cannot be done in practice - but if I am proven
wrong here, I think it's worth the money.
Cheers,
- oli
Thanks to David A Molnar for pointing out an inaccuracy in the original
posting.
Ref.:
[CS98] Ronald Cramer and Victor Shoup: A practical public key crypto system
provably secure against adaptive chosen ciphertext attack. in proceedings of
Crypto 1998, LNCS 1462,p.13ff
+-----------------------------------------------------------------+
| M. Oliver M"oller |\ _,,,---,,_ |
| Department of Computer Science /,`.-'`' -. ;-;;,_ |
| Ny Munkegade, building 540 - B3.14 |,4- ) )-,_..;\ ( `'-' |
| DK-8000 Aarhus C, Denmark '---''(_/--' `-'\_) |
| Email: [EMAIL PROTECTED] Phone: (+45) 8942 3274 |
| URL: http://www.brics.dk/~omoeller Fax : (+45) 8942 3255 |
+-----------------------------------------------------------------+
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Intel 810 chipset Random Number Generator
Date: 23 Jan 2000 23:46:15 -0700
In article <86gcjt$q1n$[EMAIL PROTECTED]>,
Michael Kagalenko <[EMAIL PROTECTED]> wrote:
> ...
> Well, I am not complaining that "cheap crystal oscillator
> hooked to a parallel port don't describe" what I am proposing.
> This part is true, it doesn't. It isn't true that I
> "postulate" high precision clock; rather, I am pointing
> out that such are readily available via the Internet, and
> that quartz crystal is alread part of every computer system, thus
> obviating the need to hook anything to a parallel port.
> ...
How do you get at those high precision clocks that are readily
available via the Internet except via NTP?
Those who are acquainted with NTP as it has been practiced on the
Internet for the last 12+ years would not expect to get much entropy
from the clock error or correction signals from NTP. From the earliest
days of NTP, it has often been reported that the temperature of machine
rooms can be inferred from NTP error signals. Who would rationally
try to get random numbers useful for encryption from NTP, when the
main "random" clock errors come from things that can be predicted and
even affected remotely, including temperature changes of the system
and lost clock interrupts due to such things as dealing with floods
of packets and fancy graphics images on web pages?
Consider also that NTP assumes that the network path between the master
and the slave has approximately symmetric delays. Judicious packet streams
that go nowhere near either the master or the slave can change how much
the symmetry assumption is wrong. Any such change is necessarily
interpreted by the NTP client as a change in how the client is ticking.
Thus, there is yet another way your enemies can manipuate your NTP error
signals.
Then there is the hassle that NTP corrections occur about once every 90
seconds. Even if your computer's crystal is so badly designed and built
that is noise does have high, unpredictable entropy, your computer's
circuitry and software are so well designed and built that lost clock
interrupts are not a problem, and it has such wonderful thermal stability
and violates the new energy conservation laws that its temperature never
changes no matter how active or idle it has been for the last few hours,
one sample every 90 seconds does not sound very useful.
There are other problems. NTP works by doing a lot of long term averaging.
Any single comparison of clocks over a network has quantization errors at
least as large as the wire occupancy of a packet. That amounts to
microseconds to milliseconds. Even if you design your own network clock
protocol, how can you get at the thermal noise in your computer's crystal
when your measurements involve millisecond quantizations?
Not many computer clocks give phase information nor allow you to
measure the frequency of the clock except by counting a lot of
oscillations. Won't that counting tend to average out much of much
of the thermal noise you might hope to measure?
In other words, as far as I can tell, while it must be true that crystals
in computers do have random thermal noise, there are other, far better
sources of true randomness in computers than naively comparing crystals.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: paul mckee <[EMAIL PROTECTED]>
Subject: Help!!!Looking for Volunteers for my Masters Degree Research
Date: Mon, 24 Jan 2000 10:52:44 +0000
Thanks for at least reading my posted message:
If you could just visit the site below and fill in the survey....
Theres no prizes or catches just the undying gratitude of a Scottish
student whodoes not want to send unsolicited mail
http://websites.ntl.com/~frances.mccormack/msc.htm
If there is any questions or you just want to bend my ear about any
errors
email me at [EMAIL PROTECTED]
Many Thanks
Paul McKee
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Challenge.
Date: 24 Jan 2000 10:48:07 +0100
In article <[EMAIL PROTECTED]>,
Doug MacKay <[EMAIL PROTECTED]> wrote:
>> Hi,
>>
>> Can anyone crack this code?
>> If you can, email me the solution.
>>
>> x11yijx24xcydx.ztlyoyaxxzilxmytyuy8x.yuytzoozoozn.zznv
>
> To save everyone's time this says:
>
> "I do not know how to read the sci.crypt FAQ on challenges"
How come the cleartext is 3 characters longer than the cryptotext?
> and is just XOR'ed against a value I dont feel like posting right now.
..which means you did use a One-Time Pad, even though you earlier
claimed you didn't....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Java's RSA implimentation
Date: 24 Jan 2000 10:48:38 +0100
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
> Paul Schlyter <[EMAIL PROTECTED]> wrote:
> : In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
> :> Paul Schlyter <[EMAIL PROTECTED]> wrote:
>
> :> [BigInteger objects are "immutable". They can't be altered once created...]
> :>
> :> : What would happen if you instead of A=A+1 tried e.g. B=A+1; A=0; ???
> :>
> :> No juice. New A (=0) object created. Old A object still floats around
> :> the system like an unwanted turd.
> :
> : OK -- what if you do:
> :
> : BigInteger A[1000000], B[1000000];
>
> Then you get compilation errors - this isn't how you declare arrays in
> Java.
Feel free to correct my syntax above. BTW my intention wasn't merely
to declare the arrays, but to also define them....
>
> : for( i=0; i<1000000; i++ )
> : A[i] = <something>;
> :
> : B = A;
> :
> : Will the B = A discard the old B and create a new copy of B?
>
> B is not now itself a BigInteger object, but a (reference to an) array
> of them.
Which means arrays aren't "first class citizens" in Java?
> While BigInteger objects are themselves immutable, a (reference to an)
> array of them is not (i.e. the answer to your question is "no" - if B
> contained no objects, no garbage would be created).
>
> B = A will discard the pointer to the old "B" array (which never
> contained any objects anyway in the example code given).
>
> If this was the /only/ pointer to B, then any BigInteger objects that
> *had* been put into B would become available for garbage collection.
>
> I'm not sure any of this helps very much with the aim of
> "total oblieration" of a BigInteger once it has been created.
So the conclusion will then be: if you want to be able to control the
security of the program, stay away from Java!
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
** 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
******************************
