Cryptography-Digest Digest #411, Volume #13 Tue, 2 Jan 01 07:13:01 EST
Contents:
Re: computing RSA keys (Francois Grieu)
Re: Idea for Independent Study Project (David A Molnar)
Re: calculating 2048 bit public key ops with an 1024 bit engine? (Aki M Suihkonen)
Re: calculating 2048 bit public key ops with an 1024 bit engine? (Paul Rubin)
Re: AES in optimized x86 assembler? (Thomas Pornin)
Re: AES in optimized x86 assembler? (Paul Schlyter)
Re: computing RSA keys ("Michael Scott")
Re: A Censorship Resistant Digital Magazine Scheme (Mok-Kong Shen)
PKCS #15 (R Pradeep Chandran)
Re: Diffie-Hellman Matrix Idea To Break (Jyrki Lahtonen)
Re: "Content Protection for Recordable Media" (Jyrki Lahtonen)
----------------------------------------------------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: computing RSA keys
Date: Tue, 02 Jan 2001 08:04:23 +0100
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Use one round of Miller-Rabin, followed by one round of Lucas-Lehmer.
The Lucas-Lehmer test I found is for Mersenne primes only.
What is that appropriate second test, and exactly why is it useful ?
Francois Grieu
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Idea for Independent Study Project
Date: 2 Jan 2001 07:29:48 GMT
[EMAIL PROTECTED] wrote:
> beginning programmer) At any rate, I'm having
> some trouble coming up with an idea that is both
> a) within the scope of my abilities and b)
> workable in the time alloted (approximately 2
> months). My original idea was to try to improve
> on existing factoring algorithms (Fermat's
What kind of discrete math and number theory background do you have?
It's difficult to tell given just that you're in BC Calc; what you
know will make a difference as to what's doable for you and what's not.
Just for starters...have you ever seen or heard of
* linear algebra?
- can you invert a matrix on a computer?
- have you heard of "normal forms"?
- have you seen a dual?
- inner products?
* modular arithmetic?
- have you ever performed modular exponentiation?
- have you written a computer program to do so?
* big-Oh notation? (e.g. O(n^2) )
- can you define what the notation means?
* a group?
- Can you show that "modular addition forms a group"?
- modular multiplication?
- Lagrange's Theorem?
- Euler's Phi function
- why is phi(n) = (p-1)(q-1) when n = pq,
p and q prime?
* a field?
* a finite field?
- have you ever constructed one?
- computed using field elements?
* an elliptic curve?
- have you ever computed in the group of points on
the elliptic curve?
* a Turing Machine?
- a "reduction" from one problem to another?
> theorem and the b-algorithm, explained in the
> Sept. 1998 issue of the College Mathematics
> Journal) but I think that may be beyond my scope.
That is almost certainly beyond your scope. I will leave it to Bob
Silverman to tell you how far beyond your scope it is. Even implementing
one of the modern factoring algorithms may be too difficult, especially in
2 months.
> A local university professor (I'm a senior in
> high school) is helping me out some, but he can't
> tell me what to do. So! Any ideas? Please e-mail
> them to [EMAIL PROTECTED] or post them here.
It's hard to say since I don't know your background. Also I don't know
what your inclination is - do you want something more mathematical, or
would you be happy with implementing a protocol already in the literature?
or replicating the results of an implementation paper?
What are the requirements of your science fair for original work?
There are lots of cute protocols "out there" which have not been
implemented AFAIK. or if they have been implemented, the implementation is
not available. Lots of digital cash schemes, "identity escrow", weird
new public key cryptosystems, key agreement schemes,
"crypto-Computing", and so on. You could
pick one and try to make it come to life.
For this look at the USENIX Security conferences, CRYPTO, EUROCRYPT,
Financial Cryptography, and Applications of Computer Security Conference.
Slimmer but still present pickings on eprint.iacr.org
Warning: many may require some kind of network programming.
Alternatively, you could look at the state of the practice for, say,
computing in a finite field. Try to figure out what the best academic and
best current practical methods are for doing various operations. Run a
bake-off. For this look at the CHES workshop held at Worcester Polytechnic
Institute and the _Handbook of Applied Cryptography_ (available free
online).
Another thing - replicate the "timing attack" developed by Paul Kocher. or
his more recent "Power analysis" attack. See papers at
www.cryptography.com
More fun (and more novel AFAIK) - implement the "reset"
attack discussed in the paper on "Resettable Zero Knowledge" on
eprint.iacr.org. I don't know if anyone's done the implementation yet.
All these projects require access to a smartcard and smartcard reader.
That may take some time unless your professor is set up to do that, so
check first.
You are unlikely to discover a new public-key algorithm. You're less
likely to discover one which is secure. So I would suggest not pursuing
that too much unless something comes to you. While you may come up with a
secure symmetric cipher, it will be years before you know one way or the
other (or anyone else does either), so that may not be a good idea either.
On the other hand, a nice, easy to read tutorial on "how to break LOKI via
differential cryptanalysis" might be interesting. I'll defer further
comment to people who know block ciphers.
Another thing (sort of ambitious) - take the article by Antoine Joux and
Jacques Stern "Lattice Basis Reduction: A Toolbox for the Cryptanalyst"
and implement. Not unless you have linear algebra, though. Also for this
you will need a black box to do the lattice reduction, such as Shoup's
NTL - http://www.shoup.net/
Maybe a practical implementation of one-time signature schemes? THese are
cute things due to Merkle, Rabin, Lampson and others which give you
signature schemes from only a one-way function. See how efficient you can
make them using SHA-1 hashing as a primitive.
Daniel Bleichenbacher and Ueli Maurer have a paper on this topic you may
find via web search.
Also check out the ACM Conference on Computer and COmunications security
for an idea of some of the projects which could meld theory and practice.
Another fun area may be looking at data havens - see
www.cypherspace.org/links.html for some links. You could take a look at
Mojo Nation to see what a micropayment market in action looks like. Maybe
write some software for them or other haven-type projects...
(I work on one of them - see http://www.freehaven.net/ for details)
That's it off the top of my head - do you have any area you're
particularly interested in?
Thanks,
-David
P.S. disclaimer - I'm an undergraduate and I have very little idea about
what projects are "hard" and which are not. So take this all with a grain
of salt.
------------------------------
From: [EMAIL PROTECTED] (Aki M Suihkonen)
Crossposted-To: sci.math.num-analysis
Subject: Re: calculating 2048 bit public key ops with an 1024 bit engine?
Date: 2 Jan 2001 08:56:08 GMT
In article <OVgByrccAHA.268@cpmsnbbsa07> "Joseph Ashwood" <[EMAIL PROTECTED]> writes:
>Well it should be fairly simple for all cases, unless you really believe
>that my 32-bit x86 architecture is handling 1kbit data all at once. Since
>you don't seem to be US based I don't know when you probably learned the
>tricks, but just use the same multiplication techniques many of us learned
>in grade school, but use base-2^512 numbers instead of base-10. That will
>give you the multiplication, and exponentiation is a simple extention. It'll
>take a bit more code than a 1024-bit exponentiation, but it'll work.
You seem to be blinded by the superiority of your 32-bit architecture
from all the facts presented. Unless the last two paragraphs were copied from
a homework, simple arithmetic should be of no concern.
Perhaps I should have mentioned, that the ME is the *only* operation
available for a user in the *core* inside a smart card. Everything
else must be calculated with a reasonable latency with an
8-bit 1MHz RISC processor.
If I'm the one who doesn't see the obvious, I apologize and humbly ask you to
show me the details.
>"Aki M Suihkonen" <[EMAIL PROTECTED]> wrote in message
>news:92ic5k$74l$[EMAIL PROTECTED]...
>> Hello!
>>
>> Given a crypto core capable of performing upto 1024 bit wide
>> (public key) modular exponentiation, is it even relatively easy
>> to extend it for operations twice the length?
>>
>> Private key ops wouldn't be a problem, thanks to CRT.
>>
>> Are there any special cases where M^B mod (N_h*2^1024 + N_l)
>> would be easy to calculate? Eg. when GCD(N_h, N_l)=1 ?
>>
--
Problems 1) do NOT write a virus or a worm program
"A.K.Dewdney, The New Turing Omnibus; Chapter 60: Computer viruses"
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: calculating 2048 bit public key ops with an 1024 bit engine?
Date: 02 Jan 2001 01:08:10 -0800
[EMAIL PROTECTED] (Aki M Suihkonen) writes:
> Perhaps I should have mentioned, that the ME is the *only* operation
> available for a user in the *core* inside a smart card. Everything
> else must be calculated with a reasonable latency with an
> 8-bit 1MHz RISC processor.
Are you sure that coprocessor doesn't also allow regular multiplication?
Every one I've seen does that.
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: AES in optimized x86 assembler?
Date: 2 Jan 2001 09:22:11 GMT
According to Paul Rubin <[EMAIL PROTECTED]>:
> because there's no portable way to do multi-precision arithmetic in C
> that uses the full capability of the PC architecture (specifically,
> multiplication instructions that give double-width products).
Actually there is one : unsigned long long. This type is at least 64-bit
wide (and usually is that wide in PC common compilers) and is standard
(since ISO 9899:1999, aka C99).
However, it appears that gcc is not very good at optimizing such code.
Besides, the Intel instruction set is a real nightmare for compilers,
so, indeed, you can get impressive speed-ups using hand-coded assembly
-- on a particular chip. An extremely good code on a Pentium MMX will
not perform that well on a Pentium II, for instance.
--Thomas Pornin
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: AES in optimized x86 assembler?
Date: 2 Jan 2001 09:22:45 +0100
In article <[EMAIL PROTECTED]>, Marc <[EMAIL PROTECTED]> wrote:
> The crypto algorithm will run 99% of execution time, because the
> intended application is a BIOS INT13h patch to retrofit on-the-fly
> encryption for harddrives under DOS/Win9x.
Ouch......
Now, if 99% of the CPU time will be spent on en/decryption, this
would imply disk access will be some 100 times slower compared to a
non-encrypted drive. Would anyone want to use this?
> No user interface no nothing, just a bare low level patch :-) Speed
> is desirable because next to resistance against selected security
> threats, the application will have no perceivable effect other than
> the more or less reduced harddrive speed.
>
> I asked for .asm because I am not an experienced x86 programmer at all
> (my focus are 8bit embedded systems) and will face enough problems
> already with a documentated .asm source where register/memory/stack usage
> is straight forward. I think this is much easier to work with (for
> me) than to try glue .c into the low level INT13h context. I already
> have a working .asm patch to wiggle the PC speaker during disk
> accesses.
Since you're hooking into Int 13h on a Win9x machine, you'll face some
problems:
1. How will you handle harddisks larger than 8 GBytes? The Int 13h
interface will only be able to address 8 GBytes.
2. Since you're hooking into Int 13h, Win-9x will detect this and go
back to 16-bit mode for each and every disk access. This alone will
slow down disk access with perhaps a factor of 2. Will users accept
this?
3. Your Int 13h patch will not work in Win-NT/2000.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: computing RSA keys
Date: Tue, 2 Jan 2001 10:37:08 -0000
"Francois Grieu" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Bob Silverman <[EMAIL PROTECTED]> wrote:
>
> > Use one round of Miller-Rabin, followed by one round of Lucas-Lehmer.
>
> The Lucas-Lehmer test I found is for Mersenne primes only.
> What is that appropriate second test, and exactly why is it useful ?
>
See http://www.eskimo.com/~weidai/lucas.html
Mike Scott
>
> Francois Grieu
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: alt.cypherpunks
Subject: Re: A Censorship Resistant Digital Magazine Scheme
Date: Tue, 02 Jan 2001 11:55:16 +0100
wtshaw wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> > I am not sure that the authorities would have to prove
> > that before demanding from you the key to decrypt. I may
> > be wrong, but it is my impression that UK is going to
> > have a situation where one has to surrender the key
> > on demand.
> Which means that demands will be made to decrypt information where the
> keys have been lost for one reason or the other. Then, you are back to
> familiar problems of proving negatives, which is not the way to acquire
> justice. But, justice is not the goal of despots anyway.
The problem of loosing one's key (or even having never
in possession of the key) has been raised in connection with
the law that the government of UK wanted to introduce, as far
as I can remember. Does anyone know the current status of
that law? Problems of different but parallel nature could
arise if projects of the category of Carnivore get realized.
M. K. Shen
------------------------------
From: R Pradeep Chandran <[EMAIL PROTECTED]>
Subject: PKCS #15
Date: Tue, 02 Jan 2001 16:42:41 +0530
Hi All,
I wanted to have some information about the types used in
PKCS #15. The document (in section 8) gives the ASN.1 definitions for
all the types defined in the document. But for that, it imports some
types from some other ASN.1 modules.
The imported modules are
UsefulDefinitions
InformationFramework
AuthenticationFramework
CertificateExtensions
ANSI-X9-62
ANSI-X9-42
PKIXCMP
Does anybody know where I can find the ASN.1 definitions of these
modules?
Thanks in advance,
Have a nice day,
Pradeep
--
R Pradeep Chandran | Tel(Off) : +91-80-8091438
Siemens Information Systems Ltd. | Fax(Off) : +91-80-8521130
#84, Keonics Electronics City, | pradeep DOT chandran AT sisl.co.in
Bangalore, India | http://www.sislindia.com/
------------------------------
Date: Tue, 02 Jan 2001 13:46:48 +0200
From: Jyrki Lahtonen <[EMAIL PROTECTED]>
Subject: Re: Diffie-Hellman Matrix Idea To Break
Simon Best wrote:
>
> David Wagner wrote:
> >
> > Simon Best wrote:
> > >Alice wants to send Bob another secret love letter. Alice and Bob both
> > >have a square matrix, M, for such purposes. Alice randomly picks a big
> > >number, a, and raises M to that power, to produce A:
> > > A = M^a
> >
> > Problem #1: These matrices will get enormous.
>
> Solution #1: Do it over a finite field.
>
Better, see below though.
> > Problem #2: The discrete log problem for random matrices over Z is easy.
> > (e.g.: note that det A = (det M)^a, so compute a as log det A / log det M.)
>
> Question #2: What if det M = the field's multiplicative identity
> element?
This helps, one way of looking at XTR is that they do something like
this
for 6x6 matrices.
>
> > Did you mean to work over some ring? (e.g., mod p?)
>
> Yes, I thought I'd mentioned that in my original post?
>
> > What motivation would there be for considering this matrix-based formulation
> > as opposed to the usual Diffie-Hellman protocol?
>
> Don't know. I didn't really post it as a serious proposal for a DH
> variant. After there was some interest in another (exceedingly weak)
> matrix idea, I thought I'd post it out of interest.
>
> (The only possible motivation I can think of for using a matrix
> implementation of DH might be computational convenience (as in matrix
> multiplications with elements of a small, finite field, compared with
> multiplications of elements of a large, finite field).)
>
Yes, this is true. However, the same applies to the security.
I am a relative newcomer to this field (and it's been a while since
I did pure algebra either), but I think that the discrete logarithm
problem of nxn-matrices over a field of q elements can be solved,
if you can solve the discrete logarithms problem for all the fields
of q^i, i at most n (and vice versa). I.e, it won't do you much good
to move from finite fields to matrices. The DL-problem won't be easy
but it will be easier than on an appropriately chosen EC for the same
group size.
> Simon
>
> --
> _______________________________________________________________________________
> Personal: [EMAIL PROTECTED]
> Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
> Everyone does their own signature to be different. How does that work?
--
Jyrki Lahtonen, Ph.D.
Department of Mathematics,
University of Turku,
FIN-20014 Turku, Finland
http://users.utu.fi/lahtonen
------------------------------
Date: Tue, 02 Jan 2001 14:03:19 +0200
From: Jyrki Lahtonen <[EMAIL PROTECTED]>
Subject: Re: "Content Protection for Recordable Media"
nobody wrote:
>
> >]the info is stored on the drive in encrypted form. you can copy the
> >]encrypted files as any other ordinary files. e.g. to a non-compliant
> >]drive.
> >
> >]to decrypt, you will need to obtain a licence to get the requisite
> >]info.
> >Nice. So they can prevent me from reading my own data? And people would
> >put up with this? sheesh.
>
> oops. i phrased this rather badly. it is stored on your drive in
> encrypted form. it is uploaded to your player which will handle the
> decryption so that the content can be played. it is the makers of the
> player which will license the technology and info needed to make the
> decryption.
But won't the hackers still be able to intercept the data, when it's on
its way to, say a PC monitor. Have a debugger copy it from the video
memory
or something? Or are you saying that decryption of a video sequence is
done
inside the monitor?
>
> --
> pel
--
Jyrki Lahtonen, Ph.D.
Department of Mathematics,
University of Turku,
FIN-20014 Turku, Finland
http://users.utu.fi/lahtonen
------------------------------
** 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
******************************
