Cryptography-Digest Digest #775, Volume #10 Mon, 20 Dec 99 21:13:01 EST
Contents:
Re: Q: transcendental pad crypto ("Tony T. Warnock")
Re: Attacks on a PKI ([EMAIL PROTECTED])
Re: Q: transcendental pad crypto ("dls2")
Re: Q: transcendental pad crypto ("dls2")
Re: Keystrokes monitored/encryption useless (Nemo Outis)
Re: Q: transcendental pad crypto ("dls2")
Not All Sophie Germain Primes Are "Safe". (Ted Kaliszewski)
Re: compression & encryption (Tim Tyler)
Re: simple rng idea (Gregory G Rose)
Re: Q: transcendental pad crypto (Tim Tyler)
Re: Code Puzzle (Jim Gillogly)
Re: Q: transcendental pad crypto (CLSV)
Re: Q: transcendental pad crypto (Tim Tyler)
Re: Q: transcendental pad crypto (Tim Tyler)
Re: Microsoft- PKI/E-comm Director Opening (Ajay Shekhawat)
Re: random numbers straight out of MS BASIC (Tim Tyler)
Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ? (Arturo)
----------------------------------------------------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Mon, 20 Dec 1999 16:13:15 -0700
Reply-To: [EMAIL PROTECTED]
dls2 wrote:
> "John Savard" <[EMAIL PROTECTED]> wrote:
> > "dls2" <[EMAIL PROTECTED]> wrote:
> >
> > >Do transcendental numbers qualify as pseudo-random, or
> > >as truely-random, for purposes of one-time pads?
> >
> > Pseudo-random, since calculating the value of a transcendental
> > number is a deterministic process. And an inefficient one, for the
> > level of security provided.
>
> If there are an infinite number of transcendental numbers, then I fail
> to see why. If the transcendental is picked randomly, then doesn't
> the resulting stream of numbers also qualify as random?
>
> Derrick Shearer
> [EMAIL PROTECTED]
How do you pick a transcendantal number at random? If one could pick an
object at random, the problem would be solved.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Attacks on a PKI
Date: Mon, 20 Dec 1999 23:09:29 GMT
> Huh?
>
> We look forward to PKI for lots of reasons that have nothing to do
with
> e-commerce. Just the ability to do away with lots of paper (that we
had to keep
> with wet signatures) is useful.
>
> Of course PKI can be valuable for strong authentication of
individuals too.
>
Dear Timothy,
Please enlighten us by telling the 'lots' of reasons to look forward to
PKI other than e-commerce.
If a CA key in a PKI is compromised (doesn't have to be a root), you
still think that stong authentication would hold?
Many certificates these days are about as strongly authentic as a
hotmail address - anyone can get one.
David
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "dls2" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Mon, 20 Dec 1999 18:19:29 -0500
"John Savard" <[EMAIL PROTECTED]> wrote:
> "dls2" <[EMAIL PROTECTED]> wrote:
>
> > I disagree. Every number is computable; it follows from
> > induction.
>
> Yes, every _integer_ is computable.
>
> As there are only aleph-null possible computer programs,
> the existence of uncomputable reals follows from Cantor's
> diagonal proof.
Um, no. Cantor's diagonal METHOD allows for the induction
of an infinite number of reals, just as there are an infinite
number of integers, with no impact on computability, other
than computations. Algorithms are distinct from answers,
and infinite is still infinite.
"Since [Cantor's diagonal] method may be applied to any
such list, we may then state that no complete list of real
numbers within any finite range may be created. Thus, there
is no one to one correspondence between the real and
natural numbers, and therefore, the real numbers must be of
a higher cardinality than the natural numbers."
http://users.javanet.com/~cloclo/cantdiag.html
------------------------------
From: "dls2" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Mon, 20 Dec 1999 18:31:19 -0500
"John Savard" <[EMAIL PROTECTED]> wrote:
> "dls2" <[EMAIL PROTECTED]> wrote:
> > "Lincoln Yeoh" <[EMAIL PROTECTED]> wrote:
> >
> > > Spend your time figuring out how to create a good and
> > > secure source of randomness which no one else can get
> > > access to.
> >
> >I give up. So tell me, how is it done, seriously?
>
> Rolling dice. Diode or resistor thermal noise, sensed
> electronically.
Physics! Physics is arguably predictable, i.e. non-random. So
how is its use really so different from the use of transcendental
numbers?
> But the one-time-pad is awkwards enough so that algorithms
> are used for encryption - but the algorithm of calulating the
> decimal expansion of a mathematical formula is not a
> particularly good one for this purpose.
Why not? It doesn't seem any worse than the use of physics.
Derrick Shearer
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Nemo Outis)
Subject: Re: Keystrokes monitored/encryption useless
Date: Tue, 21 Dec 1999 00:47:13 GMT
The practice of using telescopic lenses and video cameras to record ATM
keystrokes, while not widespread, is fairly common. Because it is the
customer at risk, not the bank, the banks don't sweat it much.
Regards,
In article <83kdfd$92g$[EMAIL PROTECTED]>, molypoly <[EMAIL PROTECTED]>
wrote:
>
>> I like to run a couple of 30AWG wire wrap wires into the plug on the
>> back of your PC and connect a Basic Stamp [
>http://www.parallaxinc.com/ ]
>> and have it record keystrokes. It's about the size of a postage
>stamp,
>> and there are cool RF transmitter modules available. This allows me
>to
>> get the NT Logon password, which no sniffer program can get. For that
>> matter. there are TX cameras that look through pinholes in your walls
>> or ceiling. I could make a video of your hands on the keyboard and
>> of what is displayed on your screen.
>>
>> If you don't secure your computer physically, I can defeat any
>security
>> system you install with little trouble.
>>
>>
> You're one sick puppy . . . what else do you do with those cameras?
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: "dls2" <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Mon, 20 Dec 1999 19:11:19 -0500
"Tony T. Warnock" wrote:
> dls2 wrote:
> > "John Savard" wrote:
> > > "dls2" wrote:
> > >
> > > >Do transcendental numbers qualify as pseudo-random, or
> > > >as truely-random, for purposes of one-time pads?
> > >
> > > Pseudo-random, since calculating the value of a transcendental
> > > number is a deterministic process. And an inefficient one, for the
> > > level of security provided.
> >
> > If there are an infinite number of transcendental numbers, then I fail
> > to see why. If the transcendental is picked randomly, then doesn't
> > the resulting stream of numbers also qualify as random?
>
> How do you pick a transcendantal number at random? If one could
> pick an object at random, the problem would be solved.
Again, how does one pick anything at random?
Is any selection really random?
Derrick Shearer
[EMAIL PROTECTED]
------------------------------
From: Ted Kaliszewski <[EMAIL PROTECTED]>
Subject: Not All Sophie Germain Primes Are "Safe".
Date: Mon, 20 DEC 99 20:06:18 -0500
12/21/1999
Not All Sophie Germain Primes Are "Safe".
It is generally assumed that moduli that are constructed
with Sophie Germain primes (SG) are "safe" in that their factoring is
difficult. While that assumption is not unreasonable there are,
it should be noted, certain exceptions. SG primes can be generated
that when used for the above purpose will fail to impart to the
moduli the expected security.
Consider primes that are generated by the following algorithm:
pk = (2^k)*p0 + (2^k - 1)
where p0 is a generating prime and k=1,2,3...
When primes pk are so generated for a single p0 but a multiple value
of k we have a chain of SG primes. A modulus that is constructed
from any two such primes from the chain will not be secure since it
can be easily factored.
Primes pk in a chain are related as follows:
j > i
pj = (2^(j-i))*pi + (2^(j-i) -1)
where pj, pi are two primes in the chain. Since the chains of such primes
are not likely to be long, a solution of a quadratic equation that results
from multiplying pj and pi is feasible.
Here is an example to illustrate the situation:
p0 = 12315449
p1 = 24630899 = 2*p0 + 1
p2 = 49261799 = 2*p1 + 1
p3 = 98523599 = 2*p2 + 1
Suppose that we construct a modulus n using p3 and p1:
p3 = 4*p1 + 3
n = p3 * p1 = 4*p1^2 + 3*p1
or
4*p1^2 + 3*p1 - n = 0
Solving the above equation we recover the prime p1.
Any comments?
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Dec 1999 00:48:08 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
: [ ... ]
:> I would have thought you should be comparing 1-1 compression with non 1-1
:> compression if you're drying to draw any conclusions about its utility.
: Apparently you either didn't read, or didn't understand what I was
: saying because that's _exactly_ what I was comparing.
If so, what makes you think you can decompress at all from a single block
of the file?
IIRC, David advocates applying his 1-1 compression to the file in both
directions - partly in order to avoid headers in the unprocessed text
translating into identical sections in the compressed file - and partly
to avoid the attack you are describing.
If this technique is employed, I'd like to the see the proceedure you use
to decompress it, after decrypting only a single block of the cyphertext.
AFAICS, you'd have to decypher all the blocks before even beginning to
decompress.
It's true that this ability to resist decompression from fragments depends
on another property of the compression, besides it being 1-1, though.
:> Brute force of the whole keyspace is only what needs to be used if there
:> is no other known attack on the block cypher. If you're /seriously/
:> trying to read the messages, it would be useful to have some other sort
:> of attack as well, to reduce the effective keyspace further.
: Of course it's useful. But, if I use, say, Twofish do you have such a
: thing available?
I believe Twofish is a relatively new cypher. I am hardly the world's
best cryptanalyst. Given these two items, the answer to your question
does not seem to me to be very important.
If Twofish finds a wider audience - and some time is spent developing
attacks on it - the question becomes more interesting.
Note that I did not say the attack had to be /directly/ on the cyphertext.
In fact there are *many* other possible ways of reducing the keyspace -
/besides/ using raw cryptanalysis on the message.
The RNG responsible for key generation may be inadequate - and capable of
being statistically predicted up to a point. Keys may be partly revealed
by measuring vibrations caused by the operator keying them in - or the may
be partly read from a distance from a user's screen by an operator using
binoculars ... and so on, and so forth.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The best way to save face is to keep the lower part shut.
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: simple rng idea
Date: 20 Dec 1999 17:17:07 -0800
In article <83ke53$9eo$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
<Ok here is an idea to play with.
<
<You have f() which returns the next number from a prng [say a Lagged
<Fibonacii generator].
<
<You then reduce it modulo 5. If the result is >= 2 then you ditch it
<otherwise return the lsb of the result. The pseudo code resembles
<
<1. a = f()
<2. if (a mod 5) >= 2, goto 1
<3. output (a mod 2)
<
<This resembles a shrinking generator to me... any ideas?
The LSB of a lagged fibonacci generator is an
LFSR, so what you have is a decimated LFSR
output. Edit Distance Correlation techniques
(see for example Golic) would let you do
divide-and-conquer on the LSB only. So your
lagged fibonacci generator would have to be
pretty big.
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Dec 1999 01:09:38 GMT
dls2 <[EMAIL PROTECTED]> wrote:
:> "dls2" <[EMAIL PROTECTED]> wrote:
:> >Do transcendental numbers qualify as pseudo-random, or
:> >as truely-random, for purposes of one-time pads?
[snip "pseudo"]
: If there are an infinite number of transcendental numbers, then I fail
: to see why. If the transcendental is picked randomly, then doesn't
: the resulting stream of numbers also qualify as random?
A "randomly picked" transcendental number would have a random decimal
expansion - a transcendental number is just a real number which is
non-algebraic.
Note that this doesn't follow directly from your argument, though.
For example, there are an infinite number of finite machines that
generate random numbers. However, the output of any one of them is
pseudo-random - *not* random.
Unfortunately, you are then left with the problem about how you are going
to pick the trenscendental number you are going to use "randomly" in the
first place.
Perhaps you could perform this random selection using a digit from a
"randomly" chosen transcendental number? ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I just took an IQ test. The results were negative.
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Code Puzzle
Date: Tue, 21 Dec 1999 01:26:40 +0000
Rich Lafferty wrote:
> When all else fails, google! Or try to google, anyhow. It's taken me
> three tries to get to the single result that a google search for the
> first line of numbers returns, and it's at
>
> http://www.discovervancouver.com/crackthecode/crackthecode.shtml
>
> and creatively entitled "Crack the Code and Win Money." No beating
Cool. Some ideas and analyses have been posted at:
http://codebuster.home.mindspring.com/FREDROOM.HTM
in the "Puzzle forum" under the title "numerical puzzle".
It doesn't appear to be Nihilist Substitution. Smart money (i.e.
Doug Gwyn's) is on a homophonic substitution. It could be a known
subtype of homophonic, such as Grandpre (my current favorite).
Note that there's a good (i.e. long enough to almost certainly be
causal) repetition, and some shorter ones that look credible.
Looking for partial repetitions that differ in one or two letters
is also a good idea, because that might help identify homophones.
We also discussed doing a brute force search for the correct plaintext
sentence in on-line encyclopedias, which (if the correct one is
on-line) is quite feasible in terms of processing power. It would
be easy to spot: find sentences of the right length as the first
level filter, then look for repetitions in the correct places. Gwyn
suggests trying to separate vowels and consonants with a hidden
Markov algorithm.
Good luck with the $2K!
--
Jim Gillogly
Highday, 1 Yule S.R. 1999, 01:14
12.19.6.14.9, 11 Muluc 17 Mac, First Lord of Night
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Date: Tue, 21 Dec 1999 01:32:12 +0000
dls2 wrote:
> "Tony T. Warnock" wrote:
>>>> "dls2" wrote:
>>>>>Do transcendental numbers qualify as pseudo-random, or
>>>>>as truely-random, for purposes of one-time pads?
>> How do you pick a transcendantal number at random? If one could
>> pick an object at random, the problem would be solved.
> Again, how does one pick anything at random?
> Is any selection really random?
The (true-)randomness you are looking for is non-computable.
See the comp.theory FAQ-list 4. Kolmogorov Complexity:
ftp://rtfm.mit.edu/pub/usenet-by-hierarchy/comp/theory/Comp.theory_FAQ
The introduction is a bit short but the book refered to
is very good and explains the problem more thoroughly.
Regards,
CLSV
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Dec 1999 01:17:26 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: But the one-time-pad is awkwards enough so that algorithms are used
: for encryption - but the algorithm of calulating the decimal expansion
: of a mathematical formula is not a particularly good one for this
: purpose.
It would be a terrible one if "real" randomness was being sought - but
it's not one that is implied by the term "transcendental number".
It is true that "PI" and "e" are well known transcendental numbers - but
it's *not* part of the definition of a transcendental number that its
digits can be generated by some finite formula.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Depression is merely anger without enthusiasm.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: transcendental pad crypto
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Dec 1999 01:37:24 GMT
dls2 <[EMAIL PROTECTED]> wrote:
: "John Savard" <[EMAIL PROTECTED]> wrote:
:> "dls2" <[EMAIL PROTECTED]> wrote:
:> > I disagree. Every number is computable; it follows from
:> > induction.
:>
:> Yes, every _integer_ is computable.
:>
:> As there are only aleph-null possible computer programs,
:> the existence of uncomputable reals follows from Cantor's
:> diagonal proof.
: Um, no. [...]
John's argument seems straight to me - given his premises.
However, the premises *may* be questionable:
It is true that there are aleph-0 possible Turing machines - but it's
possibel to model computation using an infinite number of processors
conected together in parallel, with an infinite number of inputs and an
infinite number of outputs - and what is possible for this computer to do
may exceed the capabilities of any TM.
If such a machine exists anywhere, it can compute all real numbers,
and Cantor's diagonal proof does not apply to it. Alas, it seems
likely no-one will ever know if this machine exists or not ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Be realistic: plan for a miracle.
------------------------------
From: Ajay Shekhawat <[EMAIL PROTECTED]>
Subject: Re: Microsoft- PKI/E-comm Director Opening
Date: 20 Dec 1999 20:52:36 -0500
In sci.crypt David A Molnar <[EMAIL PROTECTED]> wrote:
» [EMAIL PROTECTED] wrote:
» > I hope I am not breaking group etiquette by
» > posting this here, but I think it is highly
» > relevant and some of you may be interested...
» You know, we have no good reason to believe this is
» really from Microsoft. Why not start your PKI effort
» by signing this message ? :-)
» -David
» (no, you have no reason to believe this is from me, either)
A cursory glance at the headers indicates that the original messages
appears to have been posted from the IP 131.107.3.33 which, according to ARIN,
belongs to Microsoft.
As to why would the original poster not reveal his/her
identity, I don't know; but it is not surprising considering that
it is from Microsoft... ;-)
% whois -h whois.arin.net 131.107.3.33
Microsoft Corporation (NET-MICROSOFT)
One Microsoft Way
Redmond, WA 98052
Netname: MICROSOFT
Netnumber: 131.107.0.0
Coordinator:
Kearns, Paul (PK47-ARIN) [EMAIL PROTECTED]
(206) 882-8080 (FAX) (206) 936-7329
Domain System inverse mapping provided by:
ATBD.MICROSOFT.COM 131.107.1.7
DNS3.NW.VERIO.NET 192.220.250.7
DNS4.NW.VERIO.NET 192.220.251.7
Record last updated on 17-Jun-1996.
Database last updated on 20-Dec-1999 16:17:38 EDT.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: random numbers straight out of MS BASIC
Reply-To: [EMAIL PROTECTED]
Date: Tue, 21 Dec 1999 01:43:05 GMT
Scott Nelson <[EMAIL PROTECTED]> wrote:
: Note that the seed can't really be larger than the number
: of states in the generator.
That sounds pretty-much correct to me...
: If the generator has a period of 2^24-1, then there can only be
: 2^24-1 _unique_ seeds.
...while this seems to be a *little* bit of an over-generalisation.
It seems quite possible to me for a RNG to have a period of (2^24) - 1 ...
and yet have 2^128 different and "_unique_" seeds, each one of
which produces a different cycle of this length.
Perhaps my nitpicking does not apply to the M$ generator in question ;-)
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
A journey of a thousand miles begins with a cash advance.
------------------------------
From: [EMAIL PROTECTED]=NOSPAM (Arturo)
Crossposted-To: alt.security.pgp
Subject: Re: The 20 years periods did apply to 2 of the 3 patents. Why not for RSA ?
Date: Sun, 19 Dec 1999 15:41:09 GMT
On Fri, 17 Dec 1999 13:06:08 -0500, [EMAIL PROTECTED] wrote:
>The 3 most known patents in the encryption area are :
>
>Name Number Filed Expires
>----------------------------------------------------------------
>Diffie-Hellman 4,200,770 Sept. 6, 1977 Sept. 6, 1997
>Hellman-Merkle 4,218,582 Oct. 6, 1977 Oct. 6, 1997
>RSA 4,405,829 Dec. 14, 1977 Sept. 20, 2000
>
>The 20 years periods did apply to 2 of the 3 patents.
>Why it is not applicable to the last one ?
It is not? I think it is; it´s just that RSA is younger as
far as patents is concerned.
------------------------------
** 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
******************************
