Cryptography-Digest Digest #567, Volume #12 Tue, 29 Aug 00 18:13:01 EDT
Contents:
Re: NEWBIE!!! Zodiac killer's encryption... (John C. King)
Blowfish IC? ("Richard Sloan")
Re: On pseudo-random permutation (David A. Wagner)
4096 BIT RSA Key (No User)
Re: A little technical note about intepreters (Andrew Carol)
Re: 4096 BIT RSA Key (Tom McCune)
Re: I need ADK tampered key that PGP will not detect ADK, on it ... ("David E. Ross")
Re: Idea for creating primes (Mok-Kong Shen)
Re: Test on pseudorandom number generator. ("Niels J=?ISO-8859-1?B?+A==?=rgen Kruse")
Re: [Q] Do you know a good german newsserver for sci.crypt ? ("Jeffrey Walton")
Re: R: Test on pseudorandom number generator. (Mok-Kong Shen)
Re: A little technical note about intepreters (Mok-Kong Shen)
Re: PRNG Test Theory (Tim Tyler)
Re: PGP ADK Bug: What we expect from N.A.I. (David Hopwood)
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed ("Paul
Pires")
Re: Patent, Patent is a nightmare, all software patent shuld not be allowed (Terry
Ritter)
Re: "Warn when encrypting to keys with an ADK" (Bj�rn Persson)
Re: Serious PGP v5 & v6 bug! (Bj�rn Persson)
Re: "Warn when encrypting to keys with an ADK" (Bj�rn Persson)
Re: Number theory book ("Dann Corbit")
----------------------------------------------------------------------------
From: John C. King <[EMAIL PROTECTED]>
Subject: Re: NEWBIE!!! Zodiac killer's encryption...
Date: Tue, 29 Aug 2000 20:21:13 GMT
In article <8oeiu3$3bk$[EMAIL PROTECTED]>,
John C. King <[EMAIL PROTECTED]> wrote:
> If anyone knows of any other "solutions" I would like to know. I
> know of one other book (seems to be self published). It too
> provides a "solution" which is a result of what Kahn calls
> "hypercryptanalysis". I'll try to find it and post the book.
The book is "Times 17: The Amazing Story of the Zodiac Murders in
California and Massachusetts, 1966-1981" by Gareth Penn. It's listed
as out-of-print on Amazon.com but isn't worth trying to get unless you
want to see some really goofy cryptanalysis.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Richard Sloan" <[EMAIL PROTECTED]>
Subject: Blowfish IC?
Date: Tue, 29 Aug 2000 20:31:14 GMT
Has anyone seen a manufacturer for a Blowfish IC?
Richard.
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To: comp.programming
Subject: Re: On pseudo-random permutation
Date: 29 Aug 2000 13:45:01 -0700
David A. Wagner <[EMAIL PROTECTED]> wrote:
> The latter can be done by treating the random bits as the binary expansion
> of a random real number R in the interval [0,1). A simple strategy is to
> say that we output the integer i (where 1 <= i <= n!) if (i-1)/n! <= R < i/n!.
> Note that we don't need all the binary digits of R to determine which bucket
> R falls into; it suffices to know a finite prefix of the binary expansion of
> R, since (i-1)/n! and i/n! must differ at some bit position of finite index.
> (Or did I make some stupid mistake?)
Uhhh... As others have pointed, that doesn't always terminate in finite time.
(Oops.) I apologize for the error, and widthdraw the proposed algorithm.
------------------------------
Date: Tue, 29 Aug 2000 15:06:39 -0500
From: No User <[EMAIL PROTECTED]>
Subject: 4096 BIT RSA Key
How can I make a 4096 bit RSA Key for use in PGP 6.5.8? I tried generating one
using the Cybernights Templar 2.6.3 version. But when I import the key into
6.5.8. It says the key is invalid.
---
This message did not originate from the Sender address above.
It was posted with the use of anonymizing software at
http://anon.xg.nu
---
------------------------------
From: Andrew Carol <[EMAIL PROTECTED]>
Subject: Re: A little technical note about intepreters
Date: Tue, 29 Aug 2000 14:07:55 -0700
In article
<[EMAIL PROTECTED]>,
Daniel Leonard <[EMAIL PROTECTED]> wrote:
> Well, if you do something clever, as you say, then it worths a footpage
> note, doesn't iy ?
You are comparing apples and oranges.
Foot notes, while often on a minor or side point, are PART of the
discourse itself. Comments are ABOUT the item.
For example; A "Commentary of the Bible" would contain the text of the
bible, but in addition has an independant content which points out
things of interest, clarifies difficult points, sets out interesting
notes from the translation, etc. It can be as long as the thing it
comments on.
Footnotes are meant for minor asides which are part of the main theme
of the work.
Programs are detailed instructions to an unthinking machine. Comments
provide a much richer context suitable for humans and meant to provide
a background for a maintainer or developer.
Having worked on projects with MILLIONS of lines of code, I can assure
you that detailed comments in particularly tricky bits of code are a
wonderful treasure. I have spent countless hours hand tracing some
code which made altogether too many access to global state, trying to
figure out why it was even in the program. A few comments would have
been appreciated.
I once wrote a red/black tree and a year later when having to debug it
was quite happy that I had thought to provide little ASCII diagrams of
before/after representations of how certain transform functions would
change parts of the tree.
Comments are a good thing. Anybody who thinks they are he-man enough
to not need them has had limited experience in the real world of large
scale software development
Program is WHAT.
Comments are WHY.
Treasure the difference.
--- Andy
------------------------------
From: Tom McCune <[EMAIL PROTECTED]>
Subject: Re: 4096 BIT RSA Key
Date: Tue, 29 Aug 2000 21:09:43 GMT
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
In article <[EMAIL PROTECTED]>, No User
<[EMAIL PROTECTED]> wrote:
>How can I make a 4096 bit RSA Key for use in PGP 6.5.8? I tried
>generating one using the Cybernights Templar 2.6.3 version. But when I
>import the key into 6.5.8. It says the key is invalid.
Except for the PGP 5.5.x versions, official PGP will not use any RSA key
larger than 2048 bits. Of course, that will change in about 30 days.
=====BEGIN PGP SIGNATURE=====
Version: PGP Personal Privacy 6.5.3
Comment: My PGP Page & FAQ: http://www.McCune.cc/PGP.htm
iQA/AwUBOawnNA2jfaGYDC35EQJA4QCg/T+0fDBA3jbTu39ii7ipI5EB++EAnAzf
uWA7szmtbg+1jJwIKLI9qM5X
=l5qp
=====END PGP SIGNATURE=====
------------------------------
From: "David E. Ross" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: I need ADK tampered key that PGP will not detect ADK, on it ...
Date: Tue, 29 Aug 2000 14:18:05 -0700
Rich Wales wrote [in part]:
> "jungle" also wrote:
>
> > the rule, from the time of introduction ADK was simple
> > ... don't use it, when key has ADK, don't use key ...
> > this is the rule that everyone should follow ...
>
> Maybe, maybe not. Certainly, if two people want to assure themselves
> that no one else can possibly read the messages they are sending to
> each other, then I would agree that they should use keys without ADK's.
>
> The ADK mechanism was intended for situations in which businesses want
> their employees to be able to use PGP for work-related correspondence.
> In a situation like this, I think it is perfectly appropriate for a
> business to reserve the ability to read its employees' encrypted mes-
> sages. A company has every right to insist that an employee who wants
> true =personal= privacy should do it on his/her own time, using his/her
> own computer, with his/her separate, personal, non-work-related PGP
> key. Indeed, someone who wants true personal privacy should want to
> do this anyway.
Without any method of my employer decrypting what I have encrypted, my
employer could suffer a severe loss of valuable but encrypted data if I
were to be killed by an 18-wheeler on the freeway. To me, the
alternative to an ADK is even less acceptable than the ADK. That
alternative would be that I give my employer not only my private key (to
which my employer, as the owner of the PC, already has access) but also
my pass-phrase. Not only is this unacceptable to me personally, but it
also violates security standards that prohibit the sharing of passwords
and pass-phrases (a prohibition that, in the case of classified
government data, can be enforced under criminal law).
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea for creating primes
Date: Tue, 29 Aug 2000 23:50:13 +0200
[EMAIL PROTECTED] wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > [EMAIL PROTECTED] wrote:
> > >
> > [snip]
> > > You can test to see if a number is a genrerator by performing g^
> (p/q) !
> > > = 1 for various 'q's that divide your testing prime 'p'.
> > [snip]
> >
> > I suspect there is a printing error here. If one knows that
> > there is a q that divides p, then p is certainly not a prime,
> > isn't it? Or how should one properly interpret that phrase
> > above? Thanks.
>
> Simple typo.
>
> You have your list of smaller primes N1, N2, N3 ...
>
> then you have the value p' = 2*N1*N2*N3*N4*...
>
> Then you have the value p = p' + 1
>
> Sorry for the confusion. You are looking for a value q that divides
> the value p'
Questions:
(1) Your g is such that (g,p)=1 and g^p' = 1 and g^s != 1
for all s equal to p' divided by one of its factors?
Is that right?
(2) How much do the tests g^s != 1 help in practice (in
comparison to omitting these but retaining the other
conditions) for the purpose of finding primes?
(3) Could some of the factors of p' be equal or must they
be distinct? (In the latter case why?)
(4) What is the rationale of having the N's of the same
magnitude (the same number of bits)?
Thanks.
M. K. Shen
------------------------------
From: "Niels J=?ISO-8859-1?B?+A==?=rgen Kruse" <[EMAIL PROTECTED]>
Subject: Re: Test on pseudorandom number generator.
Date: Tue, 29 Aug 2000 17:24:46 GMT
I artiklen <[EMAIL PROTECTED]> , "Douglas A. Gwyn"
<[EMAIL PROTECTED]> skrev:
> Let's do a quick "back of the envelope" calculation.
> There are 2^(5*8) possible 5-byte keys (assuming 8 bits/byte).
> There are 10^6 keys in your Step-1 reference set.
> Each test collects 10^8 samples; for each of the samples,
> there is a 2^-40 chance that a given reference key will
> match it. So the expected number of matches is
> approximately 10^8*10^6*2^-40, which is about 91.
> The expected variance is roughly the square root of
> that (rule of thumb for rare [Poisson] events): 9.5.
>
> I don't know why other tests such as Diehard did not
> detect the poor performance of URAND and random.
Diehard runs all the tests on a ~11 MB sample, at least the version i have.
This sample corresponds to about 2.2e6 5-byte keys if we exclude the
reference set, so the expected number of matches is about 2. The sample is
just too small to separate signal from noise (on this defect).
--
Mvh./Regards, Niels J�rgen Kruse, Vanl�se, Denmark
------------------------------
Reply-To: "Jeffrey Walton" <[EMAIL PROTECTED]>
From: "Jeffrey Walton" <[EMAIL PROTECTED]>
Subject: Re: [Q] Do you know a good german newsserver for sci.crypt ?
Date: Tue, 29 Aug 2000 17:46:11 -0400
If you service provider is doing a poor job, consider changing to another
service provider. Also, you can use a web based news service such as deja's
at http://www.deja.com/usenet
When I had the same problem with my ISP, I changed to one that had better
news servers (and held messages longer).
"Runu Knips" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
What really starts nerving me as hell is that I can
read my favorite newsgroup only in pieces and
examples. I often get the situation that:
(a) I write a message, but it doesn't appear. After
a while, an answer to my message appears.
(b) I read a posting [1], and then a followup, [2].
To my surprise, that followup answers to another
posting [3] which was an answer to posting [1].
This makes it clear that I miss many postings which
magically end up in someone's /dev/null.
So does anyone have a good newsserver without these
effects ? Preferably in germany, and preferably one
which allows posting, too, because otherwise I
only can start new threads through my providers
newsserver.
Thank you in advance !
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: R: Test on pseudorandom number generator.
Date: Wed, 30 Aug 2000 00:04:47 +0200
Cristiano wrote:
>
> Mok-Kong Shen wrote:
>
> > If you need only 8 bits from a LCG having a modulus much
> > larger than 8 bits, there is practically no problem at
> > all. Divide each output by the modulus to get a real
> > number in [0,1) and multiply that with 256.
>
> This is what I understand:
> Example: output of LCG= 0x12345678 (modulus 2^32)
>
> Your method:
> 305419896 / 2^32 = .071111111111 * 256 = 18.204444
> Result = 18;
>
> My method:
> 0x12345678>>24 = 0x12
> Result = 18; It is the same! But this is very very fast!
>
> That you wrote is equivalent to: (0x12345678>>32)<<8 that is
> 0x12345678>>(32-8).
That is only true for a modulus of 2^m, not for a general
modulus. Many good PRNG's don't have modulus of that sort.
(Are you sure that your PRNG's all have modulus 2^32?)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: A little technical note about intepreters
Date: Wed, 30 Aug 2000 00:04:41 +0200
Andrew Carol wrote:
>
> In article
> <[EMAIL PROTECTED]>,
> Daniel Leonard <[EMAIL PROTECTED]> wrote:
>
> > Well, if you do something clever, as you say, then it worths a footpage
> > note, doesn't iy ?
>
> You are comparing apples and oranges.
>
> Foot notes, while often on a minor or side point, are PART of the
> discourse itself. Comments are ABOUT the item.
Sorry for disturbing. But I would suggest that this
discussion is more suited for comp.programming.
M. K. Shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: PRNG Test Theory
Reply-To: [EMAIL PROTECTED]
Date: Tue, 29 Aug 2000 21:32:05 GMT
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
[can tests produce randomness?]
: The answer is clearly no for finite rejection tests. Consider that a set of
: tests that deals only with the most recent N bits of output must enter a cycle
: with length < 2^N.
: For rejection systems that deal with all of the output (finite in each
: instance, but ever-increasing), but have a description of "random" of
: finite size must also enter a cycle (*) because a finite description of
: "random" permits only a finite criteria for choosing the next bit. The
: N-bit definition of "random" provides only 2^N fitness values. [...]
: I have not spent the time to prove that the increasing collision frequency
: actually forces a cycle, but I believe this can be shown.
Hmm.
Imagine a very bad RNG test, that likes output that goes:
101100111000111100001111100000111111000000...etc.
Since we're already assuming that the system can store and process the
history so far, I presume it can also keep track of a simple counter -
of the type that's needed to produce the above sequence.
This sequence is non-periodic - yet there appears to be no serious
problem generating it with an algorithm - since we're already assuming
we have access to an unbounded memory.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
Date: Tue, 29 Aug 2000 07:54:44 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: PGP ADK Bug: What we expect from N.A.I.
=====BEGIN PGP SIGNED MESSAGE=====
Michel Bouissou wrote:
> In any case, this "ADK / ARR" feature is a very sensible thing,
You probably meant "sensitive". "Sensible" it definitely isn't!
> as incoporating such features in a cryptosystem creates one possible
> weakness and attack path. Ralf's discovery recently proved we were
> right being worried about it.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOateEzkCAxeYt5gVAQH0xQf+OiWrfhf/SxlOhamHp+/0i9o7ZHjMUhCm
EiUJ/lSxtSu0VaGsvG+RVyIv6hbp43E4+INSdqyUpnErj//qQu+UMDmGUaKJO1g+
s+C3pGBGlmAwJKurkX+Yn2GrS4yYXD3arD/9IaRVsAtqM71O0dCdZX8r74ptSW4y
znos0DVege9kVEAN1AkRQYPy0PiByESzIQvRgMVtq8Pe4eLltSdG40yOKI/cMoVt
FaaXa03Om/ucYRv3ne7zYe2WKdm2cbzxgt80koA0Pi//byGKiWH+2ziyfpyZ3xsG
2+muPOk25uIcaMtkAny+MkUbM96cpj99/ZFV0WlE3NshXS7eilUPRw==
=q6L+
=====END PGP SIGNATURE=====
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Date: Tue, 29 Aug 2000 14:54:22 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Sundial Services wrote:
> >
> [snip]
> > In the very best of circumstances, patent law requires you to COMPLETELY
> > DISCLOSE your invention in exchange for the right to (maybe..) exclude
> > others from using it for a period of many years. That can be awful in
> > the software business because your secrets are fully exposed to
> > competitors who, likely as not, can simply "trump your trick" and have
> > you begging them for a license. Even the slightest change to your
> > algorithm can qualify as an "improvement" which is not only legal -- but
> > blocks you from adopting the improvement in your own implementation!
> [snip]
>
> I wonder in the case in question how much is actually
> 'disclosed' in the text that one can read on the web page
> cited.
The entire patent can be viewed for free or downloaded for
a modest charge at.
http://www.patents.ibm.com/
Just select patent number search and the number. It's a good
site and cross referencing the patents cited as prior art, other
co-inventors or other patents also assigned to the same
company can sometimes be revealing.
Other texts could be supplied at the authors discretion but
the patent stands or falls based on what is in it. i.e. it must teach the
method claimed. "Extra" material can't help it and isn't real important
when considering the patents merit other than a better look at the
authors intent was.
>Are there more texts about that patent that one
> can read? Or are these texts inaccessible to the public?
> Since the patent apparently has the potential of attacking
> at the very root of PK applications, if I don't err, we
> should pay due attention to the issue, I suppose.
I have to say that I'm with you on this one after a cursory look.
It appears:
1, obvious and
2, Anticipated according to the prior art,
considering the breadth of the claims granted.
Didn't mean to shock you :-)
Paul
> M. K. Shen
> ------------------------
> http://home.t-online.de/home/mok-kong.shen
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Patent, Patent is a nightmare, all software patent shuld not be allowed
Date: Tue, 29 Aug 2000 22:01:10 GMT
On Tue, 29 Aug 2000 01:13:03 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt Sundial Services
<[EMAIL PROTECTED]> wrote:
>[...]
>In the very best of circumstances, patent law requires you to COMPLETELY
>DISCLOSE your invention in exchange for the right to (maybe..) exclude
>others from using it for a period of many years. That can be awful in
>the software business because your secrets are fully exposed to
>competitors who, likely as not, can simply "trump your trick" and have
>you begging them for a license.
Yes and no. Here, "the invention" is the precise set of operations
which produce new and unobvious results. So it is necessary to
describe the code doing *those* operations, but it is not necessary to
disclose the complete program which uses that code. It is not
necessary to expose anything of proprietary interest beyond the
invention itself.
>Even the slightest change to your
>algorithm can qualify as an "improvement" which
...when it is itself patented -- *if* it can be patented...
>is not only legal -- but
>blocks you from adopting the improvement
(which should be "improvement")
>in your own implementation!
Well, either the improvement is worthy of the cost of a license or it
is not. If not, one can continue to use the previous work. If the
new work is that much better, one can license it.
It is important to realize that a patent does not grant a license to
practice. It is perfectly appropriate to grant a patent on an
improvement which requires some other in-force patent. The holder of
such a patent cannot practice his invention without license from the
fundamental patent holder. So the patent holder for the fundamental
invention is likely to hold quite an advantage in any negotiation for
license rights of improvements.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Bj�rn Persson)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: "Warn when encrypting to keys with an ADK"
Date: Tue, 29 Aug 2000 22:00:43 GMT
S.R. Heller <[EMAIL PROTECTED]> wrote:
>Based on what I was told via e-mail, and on what Phil Z. said in his
>statement, it's clear to me that the PGP folks are satisfied that we
>are being warned about the presence of an ADK. It's also clear that
>they have failed to get across to the rest of us what the warning is.
>"Oh, that's the warning?"
I agree. It's not much of a warning. If one encrypts messages every day
and sees that dialog box each time, and doesn't look very close before
clicking OK, one might not even notice that there are two recipients
instead of one (or maybe nine instead of eight).
Bj�rn Persson
------------------------------
From: [EMAIL PROTECTED] (Bj�rn Persson)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: Serious PGP v5 & v6 bug!
Date: Tue, 29 Aug 2000 22:00:43 GMT
Keith <[EMAIL PROTECTED]> wrote:
>2. PGP detached signatures can be used to protect files from being tampered
>with by letting a user know if a file has been modified. A simple opening up
>of a directory viewing program and a double clicking the filename.exe.sig will
>let you know if a executable has been changed for example
This assumes that the PGP executable itself hasn't been tampered with.
You must always have a place to store the PGP executable where your
enemies can't manipulate it, and then you could probably store other
files at that same place.
Bj�rn Persson
------------------------------
From: [EMAIL PROTECTED] (Bj�rn Persson)
Crossposted-To: alt.security.pgp,comp.security.pgp.discuss
Subject: Re: "Warn when encrypting to keys with an ADK"
Date: Tue, 29 Aug 2000 22:00:44 GMT
S.R. Heller <[EMAIL PROTECTED]> wrote:
>As you know (since you got a copy) someone from PGP has written with
>a correction of my explanation of what the option means. For the
>benefit of everyone else, the offered correction is that "Warn when
>encrypting to keys with an ADK" means "make sure I see the recipient
>dialog if there is an ADK being used," this being relevant in certain
>plugins which might not otherwise display the dialog.
>
>The point, however, is still that the option doesn't do what most
>people expect it to. Be warned.
It appears to do nothing at all to me.
I've got PGP 6.0.2i and Eudora 4.3.2 with PGP plugin. I compose a
message, click the "PGP Encrypt" button in the toolbar of the message
composition window, and then click "Queue". The right key is then
selected by email address. If that key has an ARR on it, the recipient
dialog pops up *regardless* *of* *the* *state* *of* *the* *"Warn..."*
*option* (with the recipient's key and the ADK already selected). If, on
the other hand, there is *no* ARR, then the recipient dialog does *not*
appear.
Bj�rn Persson
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Number theory book
Date: Tue, 29 Aug 2000 15:08:30 -0700
"David A Molnar" <[EMAIL PROTECTED]> wrote in message
news:8oh982$etu$[EMAIL PROTECTED]...
> John Bailey <[EMAIL PROTECTED]> wrote:
> > On Tue, 29 Aug 2000 17:21:18 GMT, [EMAIL PROTECTED] wrote:
>
> >>Hi there!
> >>
> >>I was hoping that someone would be able to recommend a good book to
serve as
> >>an introduction to number theory. I am a seventeen year old student and
> >>therefore my only exposure to the field has been through a recent
interest in
> >>cryptography. The small amount of relevant number theory that I have
learnt
> >>from the texts that I have read so far has whet my appetite.
> > If your interest is in cryptography, you need to buy Schnieier's book
> > Applied Cryptography anyway. It has a chapter on number theory for
> > cryptography which is as direct and practical as any I have found.
>
> Well, yes, it is direct and practical. Sometimes frustratingly so.
> The entry on the extended Euclidean algorithm, for instance, has
> a short blurb on what it is and then gives some C source code, without
> further explanation. This is fine if you just want something which works.
> Less fine if you are fifteen and seeing the subject for the first time.
>
> Everyone has recommended good number theory books in this thread.
> Since you mentioned that this came by way of cryptography, let me point
> out another area of math/computer science which is relevant to the subject
> (and intriguing) (and hard) -- computational complexity theory. Number
> theory is not enough by itself. Just because we have a trapdoor function
> in RSA does not mean we have a secure cryptosystem. More work is needed to
> develop a secure cryptosystem -- starting with an investigation into what
> exactly it is we mean when we say "secure" in the first place!
>
> The closest thing I know to an introductory textbook in this area is
> the set of online notes at
> http://philby.ucsd.edu/cryptolib/BOOKS/gb.html
>
> It's worth looking at as a note that there is more to cryptography than
> just number theory.
>
> If you continue in cryptography, you'll likely run into this kind of work.
> Much of it is done against a backdrop of computational complexity theory.
> So you should consider finding a book or course which introduces that
> field.
>
> Sipser's book is widely admired http://www-math.mit.edu/~sipser/book.html
> I used Lewis & Papadimitriou _Elements of the Theory of Computation_
> once upon a time. Either one might be a bit much, though.
> Some of the same ideas are in N.J. Cutland's _Computability_
> and at a much less formal level in _Godel, Escher, Bach_ by Hofstader.
The original question (strangely enough) would probably be much better
suited to news:sci.crypt instead of news:sci.math despite the "math" flavor
of the question.
I have "Number Theory -- A Programmer's Guide" by Mark Herkommer (ISBN
0-07-913074-7). The explanations are very good, but the code is icky[tm].
However, you can usually use his code as a much better starting point than
just coding the whole thing from scratch.
Here are some on-line lessons:
http://members.aol.com/~jpeschel/lessons.htm
Over on news:sci.crypt there was a fellow named James Pate Williams Jr. who
made a nice collection of C routines as the answers to exercises for several
crypto books.
Unfortunately, his web page ( http://www.mindspring.com/~pate/ ) looks to be
dead as a doornail. Anyone know what happened to it?
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. Newsgroup http://www.dejanews.com/~c_a_p
C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
** 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
******************************
