Cryptography-Digest Digest #795, Volume #10 Sun, 26 Dec 99 21:13:01 EST
Contents:
Re: Adobe Acrobat File Encryption...AAARGH!! (Boudewijn W. Ch. Visser)
Re: how good is RC4? (Tom St Denis)
Disbelief about Numbers Stations ([EMAIL PROTECTED])
Re: Bits 1 to 3 (Re: question about primes) (wtshaw)
Re: Is it a hash or a cipher? (wtshaw)
Re: Bits 1 to 3 (Re: question about primes) ("John E. Gwyn")
Re: Disbelief about Numbers Stations (Rik Maloney)
Blowfish ("Ben Humphreys")
Re: Are PGP primes truly verifiable? (Paul Crowley)
Re: Adobe Acrobat File Encryption...AAARGH!! (Paul Crowley)
Re: using salt with passwords (unix-type question) (stanislav shalunov)
Re: Bits 1 to 3 (Re: question about primes) (Matthew Montchalin)
Re: Blowfish (Kyle Morani)
Re: Blowfish (stanislav shalunov)
Re: Are PGP primes truly verifiable? (Bob Silverman)
Re: Bits 1 to 3 (Re: question about primes) (Matthew Montchalin)
Re: Are PGP primes truly verifiable? (Peter L. Montgomery)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Boudewijn W. Ch. Visser)
Subject: Re: Adobe Acrobat File Encryption...AAARGH!!
Date: 26 Dec 1999 23:21:00 GMT
On Sun, 26 Dec 1999 13:09:42 -0000, Piff <[EMAIL PROTECTED]> wrote:
>Hi There
>
>I've spent the last two weeks trying to find more information on the
>encryption method used by Adobe Acrobat but can't seem to find anything.
>
>Do they use a algorithm created by themselves or a standard method like XOR?
>I assume that as they can export the software it's restricted but other than
>that I have no idea...
>
>Could one of you kind peeps give me an idea where to look as I'm down to my
>last patch of hair!!
Two weeks ? That's a long time, assuming you mean the encryption
that can be used on pdf files.
(pdf encryption in a searchengine gives lots of links )
See http://www.foolabs.com/xpdf/ , http://www.foolabs.com/xpdf/decryption.html
and http://www.fefe.de/xpdf-0.90-fefe-diff2.gz
A very quick look at the source says RC4 and MD5 .
Boudewijn
--
+--------------------------------------------------------------+
|Boudewijn Visser | E-mail:[EMAIL PROTECTED] |
| - - | http: |
+-- my own opinions etc ---------------------------------------+
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: how good is RC4?
Date: Sun, 26 Dec 1999 23:45:29 GMT
In article <[EMAIL PROTECTED]>,
fungus <[EMAIL PROTECTED]> wrote:
> RC4(tm) is really good, but has a couple of problems:
RC4 is not a trademark.
> 1) You can never use the same password twice unless you use salt
> (*many* RC4 systems were stillborn because of this one).
Any system should be still born without the usage of salts on
passphrases or shared secrets...
> 2) There are some weak password. This is easy to avoid by throwing
> away the start of the output (the first 256 bytes is plenty).
Good idea.
> If you bear these two things in mind and code accordingly then you
> should be as safe as with any other cipher.
Any other cipher?
> See: http://www.ciphersaber.gurus.com/ for examples.
it's really simple, no need to read software... it's just
init_key()
{
x = y = 0;
for i = 0 to 255
s[i] = i;
for i = 0 to 255
y = (y + key[i] + s[i]) mod 256
tmp = s[y]; s[y] = s[i]; s[i] = tmp;
<dump some>
}
get_rc4_byte()
{
x = (x + 1) mod 256;
y = (s[x] + y) mod 256;
tmp = s[x]; s[x] = s[y]; s[y] = tmp;
return s[(s[x] + s[y]) mod 256];
}
< this is of couse pseudo-C code... >
> Note that RC4 is a trademark. The rest of the world calls it
> ARCFOUR.
It's not a TM, and call it RC4. Rivest deserves respect.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Disbelief about Numbers Stations
Date: Mon, 27 Dec 1999 00:04:19 GMT
I find it hard to believe that no one has ever attempted to track these
things down. It's as if no one knows anything about them! If they are
Morse or voice, surely some sort of DF (direction finding) should be
possible to pin them down.
Can anyone tell me if the stations move constantly, if the same voice
or hand is recognizable, what power level they appear to be using, what
cities they appear to be in, etc. Even as an amateur effort, I'm
surprised that people haven't ganged up on them to do some sort of DF...
Curiously Yours...
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Crossposted-To: sci.math
Subject: Re: Bits 1 to 3 (Re: question about primes)
Date: Sun, 26 Dec 1999 18:34:07 -0600
In article <[EMAIL PROTECTED]>, "John E. Gwyn"
<[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> > > |Matthew Montchalin wrote:
> > > |> Perhaps this would make more
> > > |> sense to me if we could somehow represent these putative
> > > |> primes in binary notation instead of decimal notion?
> > > |> For instance, why would primes ending in %1001 and %0001
> > > |> tend to occur more often than primes ending in %0111 and %0011?
> > > |Assuming Mark was talking about decimal notation, you can't
> > > |convert to binary by converting the last digit independently.
> > > How about BCD? ;)
> > Try not to confuse the issue by inserting reality, ...
>
> You're the one who needs to "get real". The question was about
> a mathematical property of primes (more with l.s. digit 9 or 1
> than 7 or 3). The suggestion about looking at the binary
> notation might be a good one, but BCD does not do that.
> This has nothng to do with the existence of hardware support
> for BCD.
You cut out the best part, as the BCD question seemed to me as
superficial, but if you choose any base to look at, so what....you are apt
to find different questions similiar to the one that was raised.
--
Only a little over a year left to go in this centrury....
Knowing this, figure that a year from now, we will
resale of the hoopla we are getting ready to see now.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Is it a hash or a cipher?
Date: Sun, 26 Dec 1999 18:47:53 -0600
In article <[EMAIL PROTECTED]>, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> >
> > I had a lengthy interresting discussion today about the tridigital
> > *cipher*. The working key of the beast is a deranged alphabet grouped
> > into 8 clumps of 3 characters and 1 group of 2 characters. These 9 groups
> > are assigned each a digit from 0 to 9. The unassigned digit is used to
> > separate words.
> >
> > I'll give the example key, if I copy it correctly, without the weird means
> > it was made:
> >
> > 0:AET 1:LMZ 2:NJW 3:GHU 4:YP 5:OIV 6:DBQ 7:RCS 8: FKX 9:(separator)
> >
> > *Encryption* means finding each letter of the message and using a digit to
> > replace it. The problem that the results can be ambigious. As English is
> > redundant in structure, the substitutions are often apparent. Since 26
> > characters and space are represented by 10 digits, lots of the randomness
> > is eaten up. The system is therefore not deterministic in nature, rather
> > depending ion context and imagination at times. A given series of digits
> > might be convertable into several real, but different words.
>
> A maybe silly or ill-posed question: The above is a many-to-one
> mapping, while homophone is a one-to-many mapping. These are 'opposite'
> to each other. Which one is in principle more effective in the sense
> of security?
>
Determinative ciphers, a correct solution is guaranteed with the right
keys, do not have ambiguity in decryption that might not be resolvable.
It is not funny if an important message gets decoded as other than the
correct plaintext. In reducing redundancy in ciphertext too much, you
increase chances for ambiguity in retrieved plaintext.
If the receiver has a set acceptable vocabulary, he will recognize wrong
and right words, but this means more key, not less. You might call such
usage as we see in the tridigital an inverse homophone if that works for
you, but I rather use terms that cover even this unfortuate cipher, be
still one just for fun. The mechanism is best used upside down to provide
encryption choices rather than decryption ones.
--
Only a little over a year left to go in this centrury....
Knowing this, figure that a year from now, we will
resale of the hoopla we are getting ready to see now.
------------------------------
From: "John E. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Bits 1 to 3 (Re: question about primes)
Date: Sun, 26 Dec 1999 18:36:10 -0600
Matthew Montchalin wrote:
> Okay, supposing we are stuck in decimal mode, then why are 1's and
> 9's at the very right less common than 3's and 7's at the very
> right?
My *guess* is that powers of the base + or - 1 should be expected
to factor fairly readily; for example, any even power of the base
minus 1 is the difference of two squares and thus factorizable.
But I don't know how to set up a "probabilistic number theory".
------------------------------
From: [EMAIL PROTECTED] (Rik Maloney)
Subject: Re: Disbelief about Numbers Stations
Date: Mon, 27 Dec 1999 00:34:13 GMT
[EMAIL PROTECTED] wrote:
>... It's as if no one knows anything about them!
This has to do with code messages sent over shortwave. Here are some sites
that explain. I don't see any big deal myself, but if you're curious about
it, these links will save you some research time:
http://www.ibmpcug.co.uk/~irdial/conet.htm
http://www.spynumbers.com/
http://www.dxing.com/numbers.htm
--
"Rik Maloney" is actually [EMAIL PROTECTED] (3128 749560).
012 3456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: "Ben Humphreys" <[EMAIL PROTECTED]>
Subject: Blowfish
Date: Mon, 27 Dec 1999 11:33:41 +1100
Does anyone know where I can get some decent info regarding the Blowfish
cipher? I've used the search engines but couldn't find anything exciting.
Thanks in advance
--
Regards,
Ben Humphreys <[EMAIL PROTECTED]>
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Are PGP primes truly verifiable?
Date: 27 Dec 1999 00:02:43 -0000
David A Molnar <[EMAIL PROTECTED]> writes:
> I know that there exist algorithms which will tell you with 100% certainty
> whether a number is prime, and run in poly time, but don't know enogh
> to go into detail on this point. :-(
ISTR hearing that those algorithms rely on the Generalised Riemann
Hypothesis, which is unproven. There may now be algorithms that don't
rely on it though.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: Paul Crowley <[EMAIL PROTECTED]>
Subject: Re: Adobe Acrobat File Encryption...AAARGH!!
Date: 27 Dec 1999 00:09:23 -0000
[EMAIL PROTECTED] (John Savard) writes:
> I remember seeing, on the Adobe site itself, a complete PDF spec; I
> was amazed that it seemed to even describe the encryption (elliptic
> curves were used, IIRC, but that's about all I remember offhand).
Nope, just a weird soup based on MD5 and RC4.
--
__
\/ o\ [EMAIL PROTECTED] Got a Linux strategy? \ /
/\__/ Paul Crowley http://www.hedonism.demon.co.uk/paul/ /~\
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: using salt with passwords (unix-type question)
Date: 26 Dec 1999 20:16:50 -0500
David Crick <[EMAIL PROTECTED]> writes:
> I'm simply looking for information (and preferably a little source
> code) on how salt is used/added to the password [hash] entry and
> then stored/verified.
On my system, crypt(3) manual page says:
The salt is used to induce disorder in to the DES algorithm in
one of 16777216 possible ways (specifically, if bit i of the salt
is set then bits i and i+24 are swapped in the DES ``E'' box
output). The key is divided into groups of 8 characters (a short
final group is null-padded) and the low-order 7 bits of each
character (56 bits per group) are used to form the DES key as
follows: the first group of 56 bits becomes the initial DES key.
For each additional group, the XOR of the group bits and the
encryption of the DES key with itself becomes the next DES key.
Then the final DES key is used to perform count cumulative
encryptions of a 64-bit constant. The value returned is a
NUL-terminated string, 20 bytes in length, consisting of the
setting followed by the encoded 64-bit encryption.
Your system's crypt(3) man page should probably explain something
similar (the traditional DES hash implementation is the same for any
Unix; newer MD5 and Blowfish hashes are different, of course).
One of the implementations can be viewed at:
http://www.OpenBSD.org/cgi-bin/cvsweb/src/lib/libc/crypt/crypt.c?rev=1.13
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Bits 1 to 3 (Re: question about primes)
Date: Sun, 26 Dec 1999 17:14:34 -0800
|Matthew Montchalin wrote:
|> Okay, supposing we are stuck in decimal mode, then why are 1's and
|> 9's at the very right less common than 3's and 7's at the very
|> right?
On Sun, 26 Dec 1999, John E. Gwyn wrote:
|My *guess* is that powers of the base + or - 1 should be expected
|to factor fairly readily; for example, any even power of the base
|minus 1 is the difference of two squares and thus factorizable.
Oh! Aha, hm... Okay, now that you put it that way.... But I'm still
not sure. That is a very interesting proposition put that way.
|But I don't know how to set up a "probabilistic number theory".
Aside from generating primes one after another, and plotting the results
on a grid of some kind, and see where it goes from there?
------------------------------
From: [EMAIL PROTECTED] (Kyle Morani)
Subject: Re: Blowfish
Date: Mon, 27 Dec 1999 01:19:44 GMT
"Ben Humphreys" <[EMAIL PROTECTED]> wrote:
>Does anyone know where I can get some decent info regarding the Blowfish
>cipher? I've used the search engines but couldn't find anything exciting.
Bruce Schneier seems to know a little about it. Try his site here:
http://www.counterpane.com/blowfish.html
--
"Kyle Morani" is actually [EMAIL PROTECTED] (4903 871256).
0123 456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: Blowfish
Date: 26 Dec 1999 20:23:20 -0500
"Ben Humphreys" <[EMAIL PROTECTED]> writes:
> Does anyone know where I can get some decent info regarding the Blowfish
> cipher?
General info:
http://www.counterpane.com/blowfish.html
Implementations in C:
http://www.openbsd.org/cgi-bin/cvsweb/src/lib/libc/crypt/blowfish.c?rev=1.13
ftp://ftp.ox.ac.uk/pub/crypto/misc/libbf-0.7.2m.tar.gz
> I've used the search engines but couldn't find anything exciting.
That's strange. Right the first link on Google gets what you need:
http://www.google.com/search?q=blowfish
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Are PGP primes truly verifiable?
Date: Mon, 27 Dec 1999 01:25:02 GMT
In article <845qc6$fcm$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Schlyter) wrote:
> In article <845jup$n5a$[EMAIL PROTECTED]>, Bob Silverman
> >>> No. Suppose you generate p anq as random 512 bit primes
> >>> and (horror!) it turns out that p is the product of a 200 and a 312
> >>> bit prime. The product pq is not any easier to factor in this case than
> >>> if p and q were both prime.
> >>
> >> Are you really seriously claiming that the difficulty in factoring a
> >> number is independent of the size of the factors?
> >
> > Yes.
>
> Then I ask you to think again. Don't you think that e.g. 2^511 will
> be much faster to factor than the product of a 200-bit and a 312-bit
> prime?
Are you being deliberately stupid? Or are you merely being
obtuse?
(1) One does not apply a factoring algorithm to a perfect power.
There is no need.
(2) IF I were to (say) apply the Number Field Sieve to 75!
(75 * 74 * ....) it would take as long to factor this number as it
would any other 110 digit number. NFS and QS do not care
about the size and number of factors possessed by the modulus.
The time for them to succeed depends ONLY on the size of the
modulus. How many times do I have to say this before it sinks in?
And while ECM will pull out small factors rather easily, it can't touch
anything above about 60 decimal degits. Thus, any integer which
is the product of two (or more) primes each possesing at least 200
bits, the only algorithms we have that will do them are NFS and QS.
And their run time is independent of the size of the factors.
A 1024 bit number, which is the product of 4 256-bit primes is not
any easier to factor than is one which is the product of two 512-bit
primes.
The subject under discussion here (or maybe you've forgotten?)
is what happens if we construct an RSA modulus N = pq and
our primality test failed so that p turns out not to be prime so that
wer get N = pqr or maybe n = pqrs.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Bits 1 to 3 (Re: question about primes)
Date: Sun, 26 Dec 1999 17:49:07 -0800
Reply-To: Matthew Montchalin <[EMAIL PROTECTED]>
On Sun, 26 Dec 1999, wtshaw wrote:
|In article <[EMAIL PROTECTED]>, "John E. Gwyn"
|<[EMAIL PROTECTED]> wrote:
|> The question was about a mathematical property of primes (more with
|> l.s. digit 9 or 1 than 7 or 3). The suggestion about looking at the
|> binary notation might be a good one, but BCD does not do that. This
|> has nothng to do with the existence of hardware support for BCD.
|
|You cut out the best part, as the BCD question seemed to me as
|superficial, but if you choose any base to look at, so what....you
|are apt to find different questions similiar to the one that was raised.
Yes, if we choose any given base, is there a way of guessing (!)
the probability of the last significant digit of a given nth prime in any
given base? For instance, if we *can* figure this out for at least one
base, we should be able to figure it out for any base.
So let's start with a binary expression then. If we *can* figure it out
for binary, we can figure it out for *any* number base.
Are there any shortcuts available to us by considering digits used in
expressing the reciprocal of any given prime? For instance, the
reciprocals of the first seven primes are:
__n__ Pr(n) Reciprocal of Value Binary
1 1 1.0000 1.0000
2 2 0.5000 0.1000
3 3 0.3333+ 0.01?
4 5 0.2000 0.001?
5 7 0.1428 ?
6 11 0.0909 ?
7 13 0.0769 ?
Well, shoot, I was trying to write out the binary equivalents of
the reciprocals, calculating it in my head, but as you can see,
I gave up after a while. Anyway, if you were following me, is there
anything to be gained by looking at the first few significant digits
to the right of the decimal point, ignoring the leading zeroes?
Wouldn't this be the "flipside" of the other problem a message or two
ago?
------------------------------
Crossposted-To: talk.politics.crypto
From: [EMAIL PROTECTED] (Peter L. Montgomery)
Subject: Re: Are PGP primes truly verifiable?
Date: Mon, 27 Dec 1999 01:44:16 GMT
In article <845qc6$fcm$[EMAIL PROTECTED]>
[EMAIL PROTECTED] (Paul Schlyter) writes:
>In article <845jup$n5a$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>> In article <844jil$f0d$[EMAIL PROTECTED]>,
>> [EMAIL PROTECTED] (Paul Schlyter) wrote:
>>> In article <8433nt$60r$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
>>>>> But since the modulus would contain
>>>>>> smaller factors, it would be easier to factorise.
>>>> No. Suppose you generate p anq as random 512 bit primes
>>>> and (horror!) it turns out that p is the product of a 200 and a 312
>>>> bit prime. The product pq is not any easier to factor in this case than
>>>> if p and q were both prime.
>>> Are you really seriously claiming that the difficulty in factoring a
>>> number is independent of the size of the factors?
>> Yes.
>Then I ask you to think again. Don't you think that e.g. 2^511 will
>be much faster to factor than the product of a 200-bit and a 312-bit
>prime?
A better approximation is that the time to factor a product
is independent of the factor sizes if the factors exceed
the cube root of the product. This would apply to a 512-bit product
with 200-bit and 312-bit prime factors (cube root has 171 bits),
but not to a 512-bit product with several 2-bit (or 100-bit) prime factors.
The major known algorithms for factoring hard numbers are ECM
(elliptic curve method) and GNFS (general number field sieve).
The largest factor found by ECM so far is a 53-digit prime factor
of 2^677 - 1, by Conrad Curry. The largest GNFS factorization is
RSA-155 (512 bits) by The Cabal. To a first approximation,
the time ECM needs to find a factor depends upon the size of the factor,
but the time taken by GNFS depends upon the size of the product.
Huge amounts of machine time have
been invested in both algorithms, although ECM probably gets more use
since it is easier to program and needs little disk space.
53 digits is about one third of 155 digits.
Numerous factors over 40 digits have been found by ECM
(but one is still proud to discover another).
It is now routine to factor arbitrary 120-digit numbers by GNFS
(but this may take a few CPU-months).
I find it hard to predict whether we will get a 70-digit ECM factor
before we factor a hard 200-digit digit number by GNFS.
--
E = m c^2. Einstein = Man of the Century. Why the squaring?
[EMAIL PROTECTED] Home: San Rafael, California
Microsoft Research and CWI
------------------------------
** 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
******************************
