Cryptography-Digest Digest #583, Volume #13 Sun, 28 Jan 01 23:13:01 EST
Contents:
Re: Dynamic Transposition Revisited (long) (Mok-Kong Shen)
Re: proving x^ed mod n = x ([EMAIL PROTECTED])
Re: William's P+1 ("Michael Scott")
Re: Why Microsoft's Product Activation Stinks (Matthew Montchalin)
Re: Why Microsoft's Product Activation Stinks (Matthew Montchalin)
Re: finding inverses and factoring (Paul Crowley)
Re: Why Microsoft's Product Activation Stinks (Bill Unruh)
Re: Cryptographic Windows APIs or OCX? (David Hopwood)
Re: Mr Szopa's encryption (was Why Microsoft's Product Activation Stinks) (Taneli
Huuskonen)
Re: Primality Test ("Matt Timmermans")
Re: Primality Test ("Matt Timmermans")
Re: "Enigma" at Sundance (John Savard)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Sun, 28 Jan 2001 23:50:48 +0100
Terry Ritter wrote:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
>
> >Terry Ritter wrote:
> >>
> >> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >>
> >> >[...]
> >> >I suppose you have a different and problematical concept
> >> >of the (THEORETICAL) OTP. The bit sequence of OTP is by
> >> >definition/assumption unpredictable. If a 'claimed' OTP
> >> >uses a predictable bit sequence and consequently is weak
> >> >as you said, then it is by definition NOT an OTP, though
> >> >snake-oil peddlers used to call that OTP.
> >>
> >> OK, then, in practice, there can be no OTP at all, since, in general,
> >> it will be impossible to prove in practice that any bit sequence
> >> actually is unpredictable.
> >>
> >> Clearly we can't compare a cipher which is designed to work in
> >> practice to one which cannot. Yet that was exactly what you tried to
> >> do.
> >
> >The last sentence is FALSE.
>
> Really?
>
> From: Mok-Kong Shen <[EMAIL PROTECTED]>
> Newsgroups: sci.crypt
> Subject: Re: Dynamic Transposition Revisited (long)
> Date: Fri, 26 Jan 2001 23:26:55 +0100
> Message-ID: <[EMAIL PROTECTED]>
>
> "But the point is whether your DT is on a par with the
> theoretical OTP or perhaps better than it. So it is a
> 'theoretical' question, not a technical question."
>
> >It was you who made a comparison
> >of your DT with the OTP and claimed even superiority over
> >it.
>
> From the "Revisited" article:
>
> "When every plaintext block is exactly bit-balanced, any
> possible plaintext block is some valid bit-permutation of
> any ciphertext block. So, even if an opponent could
> exhaustively un-permute a ciphertext block, the result
> would just be every possible plaintext block. No particular
> plaintext block could be distinguished as the source of the
> ciphertext. This is a form of balanced, nonlinear combining
> of the confusion sequence and data block: as such, it is
> related to XOR, Latin squares, Shannon "perfect secrecy,"
> and the one-time-pad (OTP).
>
> "The inability to distinguish a particular plaintext, even
> when every possibility is tried, is basically the advantage
> claimed for the OTP. It is also an advantage which the OTP
> cannot justify in practice unless we can prove that the OTP
> keying sequence is unpredictable, which generally cannot be
> done. That makes the practical OTP exceedingly "brittle":
> if the opponents ever do gain the ability to predict the
> sequence, they may be able to attack many messages, both
> future and past. That would occur in the context of a
> system supposedly "proven" secure; as usual, the user would
> have no indication of security failure.
>
> "Dynamic Transposition does not need the assumption of
> sequence unpredictability, because the sequence is hidden
> behind a multitude of different sequences and permutations
> which all produce the same result. And if the sequence
> itself cannot be exposed, exploiting any predictability in
> the sequence will be difficult. (This of course does not
> mean that Dynamic Transposition cannot be attacked:
> Brute-force attacks on the keys are still imaginable, which
> is a good reason to use large random message keys.)"
>
> So exactly what about "an advantage which the OTP cannot justify in
> practice" do you not understand?
I was referring to your claim in the 'original' thread of
DT where you claimed superiority of DT over OTP. Apparently
you have forgotten what you have written at that time
and in particular of what John Savard commented to that
point. See the quote below.
>
> >John Savard first wrote some lines on that and came
> >back to it in a recent follow-up. I suggest that you leave
> >out everything in that direction in your writings about DT.
> >No reasonable man would have any internal reaction, when a
> >girl says she is pretty. Things only become different, when
> >it concerns the most beautiful creature of the world.
>
> It is your delusion that OTP is that "most beautiful creature." In
> practice an OTP is nothing more than a stream cipher with a
> particularly inconvenient key. It is only the *theoretical* OTP -- an
> illusion which cannot protect real data -- which could be called
> "beautiful" -- but that can't be used.
>
> The reason people want to use -- in practice -- an OTP is to get a
> mathematical proof of strength. Unfortunately, the OTP proof
> *assumes* a random sequence. Now, surely there can be no debate about
> whether or not an "OTP" is secure if the keying sequence is
> predictable. Also there should be little if any debate about whether
> or not we can, by testing, *prove* a keying sequence is not
> predictable. (Note that even a complex and random-like sequence
> produced by stepping a counter into the cipher of your choice is
> predictable -- if someone can just reverse that cipher. And whether
> or not we can do that is irrelevant; for a proof of strength, we need
> to know that no opponent can do it, and that is something we cannot
> know.) So the OTP proof simply does not apply in practice, unless we
> have some way to *prove* sequence unpredictability to cryptographic
> levels of assurance.
I have no delusion about the theoretical OTP. I know that
it is a theoretical construct that can never be (exactly)
obtained in practice, though approximated, and that there
are big and essential difficulties of employing even its
'approximations'. But it was you who first brought the
term OTP into the thread you initiated. Given that,
OTP can be (allowed to be) discussed in connection
with the claim you made in the original thread, isn't it??
>
> >> >Some people in
> >> >crypto groups even object to use the term pseudo-OTP to
> >> >designate that kind of stuff.
> >>
> >> Usually the objection is to using an obvious pseudo-RNG and calling
> >> the result an OTP instead of a Stream Cipher.
> >>
> >> >(Once I got flames for having
> >> >employed the term pseudo-OTP.) We should take care not to
> >> >be contaminated in our terminology by the slangs of
> >> >snake-oil peddlers. (Of course they could complain, because
> >> >anything used 'one-time' is OT, but that's evidently outside
> >> >our present concern.)
> >> >
> >> >BTW, my argumention in the previous follow-up could be
> >> >simplified a bit. One does not have to use the big sequence
> >> >S. It suffices to pick one arbitrary balanced block and
> >> >feed repetitions of it to the algorithm. Basically, the
> >> >argument boils down to the trivial fact that a PRNG has a
> >> >finite period, while the theoretical OTP has, by definition,
> >> >an infinite period. Hence there is no chance that the former
> >> >can compete with the latter.
> >>
> >> Had you actually read my "Revisited" article, you would have found the
> >> statement:
> >>
> >> "This of course does not
> >> mean that Dynamic Transposition cannot be attacked:
> >> Brute-force attacks on the keys are still imaginable, which
> >> is a good reason to use large random message keys."
> >>
> >> I am discussing a cipher which functions in practice, not some
> >> theoretical thing whose only use is to confuse and confound.
> >>
> >> You appear to be discussing perfection which can never occur in
> >> practice.
> >
> >Ah, I admit that I haven't carefully read your revision
> >(because of your previous comparion with OTP, which has
> >unfortunately relaxed my attention somewhat). But you
> >should have retracted your claim of superiority over OTP
> >in the revision, I suppose, in order to avoid confusion
> >of readers.
>
> How about this:
>
> Dynamic Transposition (a practical cipher) is arguably superior to the
> OTP (when used in practice), because under known-plaintext attack an
> OTP is immediately vulnerable to a predictable keying sequence, while
> Dynamic Substitution hides predictability behind a vast number of
> different permutations, each of which could have created the given
> ciphertext block.
I would in your place omit reference to OTP in connection
with DT entirely. This would completely avoid a point that
John Savard raised. See one of his follow-ups today.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: proving x^ed mod n = x
Date: 28 Jan 2001 17:59:24 -0500
[EMAIL PROTECTED] wrote:
> e.g. n=45=9*5: phi(n)=pi(9)*pi(5)=24 and x^(24)=x mod 45 if x is
> relatively prime to 45 (actually x^(12)=x mod 45: one only use the
> least common multiple of phi(9)=6 and phi(5)=4 instead of the
> product) BUT 3^24<>3 mod 45 (if 3^24=3 mod 45, then 3^45=3 mod 9 but
> 3^45=0 mod 9 and 3<>0 mod 9).
Should be:
...
product) BUT 3^24<>3 mod 45 (if 3^24=3 mod 45, then 3^24=3 mod 9 but
3^24=0 mod 9 and 3<>0 mod 9).
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: William's P+1
Date: Sun, 28 Jan 2001 23:02:09 GMT
"Mika R S Kojo" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> "The Death" <[EMAIL PROTECTED]> writes:
> >
> > Seems there s no reason for me to use it then.
> > Is it in any way better than Pollard's P-1 ?
>
> In the trivial sense yes. It finds a factor p of N if p+1 has small
> divisors, but Pollard's p-1 finds such that p-1 has small divisors :)
> ....
In fact so-called (p+1) is in fact a (p+ or -1) method, so in a sense it
supplants (p-1). But its a little slower.
Mike Scott
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: or.politics,talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Sun, 28 Jan 2001 15:03:29 -0800
On Sun, 28 Jan 2001, phil hunt wrote:
|On Sun, 28 Jan 2001 01:23:16 -0800, Anthony Stephen Szopa
|<[EMAIL PROTECTED]> wrote:
|>I always appreciate your replies but I see no way around this:
|>MS products perform.
|
|MS products perform their intended function very well. Their
|intended function is to separate punters from their money.
|
|Unfortunately, their products are not so good when viewed as
|computer software. Consider MS recently had 2 24 hour outages due
|to inadequacies in IIS and NT. Or consider Netcraft's
|(www.netcraft.co.uk) list of the websites with the most uptime --
|94% ran Apache, 0% ran IIS or NT.
Be that as it may, I'd like to see Anthony get his day in court.
If Microsoft actually ripped him off --- God knows why --- then
by all means, let him have his day in court.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: or.politics,talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Sun, 28 Jan 2001 15:05:26 -0800
On Sun, 28 Jan 2001, phil hunt wrote:
|I forget to mention here that MS are now running Linux on some of their
|DNS servers, according to some reports. Apparently the MS DNS system
|wasn't up to the job.
Strangely both funny and tragic.
------------------------------
Subject: Re: finding inverses and factoring
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Mon, 29 Jan 2001 00:27:15 GMT
David A Molnar <[EMAIL PROTECTED]> writes:
> I recall that in RSA, knowledge of d alone, combined with e and n, is
> enough to derive phi(n) and factor. I don't recall the proof,
> unfortunately
It's covered in the Handbook of Applied Cryptography, chapter 3 I
think.
http://www.cacr.math.uwaterloo.ca/hac/
cheers,
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: or.politics,talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: 29 Jan 2001 02:06:50 GMT
In <[EMAIL PROTECTED]> Anthony Stephen Szopa <[EMAIL PROTECTED]> writes:
>Their is a certain level at which MS's anti-piracy "innovation" will
>be worth it. I think the break even will be if MS stops as little
>as one or two percent of its OS piracy. And I think their scheme
>will accomplish this and much more.
Actually no. This is the typical response of bureaucrats-- if something
bad happens, insitutute procedures to stop it from happening. Thus if
pilfering of supplies from the storeroom occurs, hire someone to man the
storeroom. While it may lower pilfering, the cost of the salary etc of
the stores man is rarely counted in. Nor is the additional inefficiency
to the organisation, as people are put to inconvenience.
The industry likes to parade those unpaid for licenses as losses.
Unfortunately at the boundary where they are operating as many people
just barely are willing to pay as do not pay. thus these additional
pains that this procedure drives the consumer to will tip many over into
not bothering, as well as getting some of those who do not pay to pay.
And get a bunch to say-- shit, lets look at this Linux thing.
This is especially true since a lot of what they make money on these
days are upgrades-- Win95->98->2000/me, Office 6->7->8->2000->??
All it takes is for a few to say forget it to loose all they gain.
>I think it is a no brainer that MS will do all it can to protect
>its revenue and power and will forcefully attempt to thwart any
>competition for another anti-piracy scheme even if it is obviously
>better.
??? They make no money off the antipiracy scheme itself. I do not see
how they can control the market for antipiracy schemes.
------------------------------
Date: Mon, 29 Jan 2001 02:53:04 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Cryptographic Windows APIs or OCX?
=====BEGIN PGP SIGNED MESSAGE=====
Augusto Jun Devegili wrote:
>
> Quoted from MSDN Library:
>
> "Secure Channel (S-Channel) is a security service provider module that
> implements the popular public key security protocols between Web clients
> and servers. These include SSL, PCT, and TLS (an upcoming standard that
> merges SSL and PCT).
In the interests of accuracy, I should point out that TLS owes little or
nothing to PCT; it is strictly a revision of SSL.
- --
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
iQEVAwUBOnTGTTkCAxeYt5gVAQFQ/Qf7BJYpiWBvA3HBI1kyOnqOLZSjGDPe450H
PMu+hqZ6a4xCVsjNTmbm4BLjbuLmyFBu8WG60Xyl1n7SEYNyp41CDkbG/7ofkF84
WlRCupReh8DDMk+Gt7BigyREuZhH2kTOjqmW8mnS3q398lvsDN6gPTQ1TVGdJaDe
5MVkh8vPi/5mfKvVK0LqPmnTjNfPGij65UjKEOaXYRYcGO7hOsSSweWCzBS+K4RR
v5E8JF2WskKSPY/IgVaExwQl+C9oZAuVlMIyrBkkOETYJDY1mEEj8+sTa7g8BVWr
eAGVGf1UpIxVISaL82EzVlEDh13KtBHO9DfTksC+sKc3i52xmwhrVQ==
=L5HW
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Taneli Huuskonen)
Crossposted-To: talk.politics.crypto
Subject: Re: Mr Szopa's encryption (was Why Microsoft's Product Activation Stinks)
Date: 29 Jan 2001 05:29:38 +0200
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
In <[EMAIL PROTECTED]> Anthony Stephen Szopa
<[EMAIL PROTECTED]> writes:
[...]
>Answer us this: where are you proposing getting the raw random digit
>output from the random number generator to break someone's key?
In three steps:
1. Assume the cryptanalyst has enough known plaintext. For instance,
the encrypted file might be a backup archive of a hard disk containing
mainly publicly readable files. This yields a large amount of known
bytes in the pseudo-OTP.
2. Assume the cryptanalyst can guess _part_ of the key - the part
that describes how the raw pseudorandom bytes are shuffled after they've
been generated. This could well happen, if the user had originally
planned to generate, say, 2000 bits' worth of random numbers by shaking
beans out of a bottle, but gave up after only 1000 bits. This is
against your recommendations, but you don't stress the point and you
don't give any reasons.
Now, the cryptanalyst can reconstruct large parts of the pseudorandom
byte stream, but as you point out, this isn't enough.
3. I hinted at this, but didn't really make it explicit before. You
don't actually need a large number of the pseudorandom digits to be able
to predict some others. You just need to have a couple dozen digits,
but they have to be from the right positions. Hence, guessing which
position in the digit stream corresponds to a given position in the byte
stream would be enough. Then, you'd usually know two digits for each
byte and have a good idea of what the third one might be. Repeating
this guess for several consecutive bytes in three or four different
(and quite widely spaced) places may or may not be possible with
today's computers, for all I know.
I've no real information on the feasibility of Step 3; I'm not
knowledgeable enough in cryptology even to estimate the amount of
computing power required. However, if it can be done, then preventing
the adversary from taking Step 2 is crucial. Moreover, if you can't
_prove_ that Step 3 is impossible, then you should absolutely stress the
importance of thoroughly shuffling the pseudorandom bytes after their
generation, and explain why, in the documentation of your programme.
Taneli Huuskonen
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.0i for non-commercial use
Charset: noconv
iQA/AwUBOnTjfl+t0CYLfLaVEQLacACeP2dcZJWyPBVXElMiPD7FevpV854AoPpS
9ju+3sTVDcD8uUmnz2KAy+oo
=DwLy
=====END PGP SIGNATURE=====
--
I don't | All messages will be PGP signed, | Fight for your right to
speak for | encrypted mail preferred. Keys: | use sealed envelopes.
the Uni. | http://www.helsinki.fi/~huuskone/ | http://www.gilc.org/
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Mon, 29 Jan 2001 03:37:54 GMT
The only thing I can think of that would make a a Miller-Rabin test that
slow is calculating the exponential the hard way -- are you doing it with
~768 multiplications, or ~2^512 ?
"Adam Smith" <[EMAIL PROTECTED]> wrote in message
news:8I%c6.3988$[EMAIL PROTECTED]...
> Once again, this is for generating RSA keys...if all of my posts here are
> getting annoying or are out-of-place, please say something....
>
> I'm not having trouble generating random numbers with 150-200 digits, my
> problem comes in testing to see if they're random...I'm using an
> implementation of the Rabin-Miller primality test with even only one round
> (if true then probability that the number is composite is < .25^(number of
> rounds)), but it's taking an extremely long time to test...I had to force
> close the app before it even tested one number (it's using a Pentium III
500
> MHz chip)...
>
> Any tips on generating 512 bit prime numbers?
>
> Once again, thanks in advance!
> Adam Smith
>
>
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Primality Test
Date: Mon, 29 Jan 2001 03:42:08 GMT
It might also be that slow if you are waiting until after all the
multiplications to do the modular reduction -- your numbers would get pretty
big. You should perform the reduction after every multiplication.
"Matt Timmermans" <[EMAIL PROTECTED]> wrote in message
news:mA5d6.13$[EMAIL PROTECTED]...
> The only thing I can think of that would make a a Miller-Rabin test that
> slow is calculating the exponential the hard way -- are you doing it with
> ~768 multiplications, or ~2^512 ?
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: rec.arts.movies.current-films
Subject: Re: "Enigma" at Sundance
Date: Mon, 29 Jan 2001 03:49:45 GMT
On Sun, 28 Jan 2001 15:56:12 GMT, DRO <[EMAIL PROTECTED]>
wrote, in part:
>The film
>stars Dougray Scott as Tom Jericho, one of the genius's that broken the
>Enigma code, but now the German's have changed the code again. With out
>the new code, the allied shipping can be attacked by the German U-boats
>without warning. Jericho is also becoming involved with the mysterious
>and seductive Claire (Saffron Burrows) who also works for the Allies.
>Things get complicated when Claire disappears and Tom sets out to solve
>the mystery with the help of Kate Winslet, Claire's housemate.
Kate Winslet? Yes, definitely not an 'indie' film of the typical kind.
And the character "Tom Jericho" tells me the movie is based on the
novel "Enigma" by Robert Harris, a major literary property.
I'd call this one a must-see, indeed.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
