Cryptography-Digest Digest #925, Volume #13 Sat, 17 Mar 01 09:13:01 EST
Contents:
Re: Factoring RSA (Mok-Kong Shen)
A literature pointer on anonymity and unobservability (Mok-Kong Shen)
Re: OT: TV Licensing - final answer - sorry for xpost (David Hayward)
Re: NTRU, continued... ("Sam Simpson")
Re: qrpff-New DVD decryption code (Paul Schlyter)
Re: Factoring RSA (Paul Schlyter)
Re: Factoring RSA (Paul Schlyter)
Re: Computing power in the world (Paul Schlyter)
Re: Computing power in the world (Paul Schlyter)
Re: Computing power in the world (Paul Schlyter)
Re: Defining a cryptosystem as "broken" (Paul Schlyter)
Re: primes for Blum Blum Shub generator ("Dobs")
Re: IP (those who know me have no need of my name)
Re: Q: IP (those who know me have no need of my name)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Factoring RSA
Date: Sat, 17 Mar 2001 11:16:35 +0100
Mok-Kong Shen wrote:
>
> Michael Brown wrote:
> >
> > I know I'm getting repetitive, but could someone also look at my factoring
> > page :P
> >
> > http://odin.prohosting.com/~dakkor/rsa/
>
> Why don't you try it yourself on one of the RSA challenges?
> Another suggestion is that you provide a short succint
> description of the method.
Addendum:
I meant you try one that has already been solved. Currently
you have to do some search in archives to find these numbers,
unfortunately.
I have just been called attention to a seemingly not
uninteresting fact: The RSA factoring challenge went away
several months ago. Since then there is only the message:
Look for the new and improved RSA Factoring Challenge soon!
but nothing has yet happened.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: A literature pointer on anonymity and unobservability
Date: Sat, 17 Mar 2001 11:37:53 +0100
I like to call attention of those interested in the issue
to a new book:
H. Federroth (ed), Designing Privacy Enhancing Technologies.
LNCS 2009, Springer, 2001.
It contains among others a paper co-authored by David Molnar.
M. K. Shen
------------------------------
From: David Hayward <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: OT: TV Licensing - final answer - sorry for xpost
Date: Sat, 17 Mar 2001 11:06:31 +0000
Reply-To: [EMAIL PROTECTED]
On or around 8 Mar 2001 16:42:18 GMT, this enlightening missive was
received from [EMAIL PROTECTED] (Richard Herring)
>In article <WOtp6.930$[EMAIL PROTECTED]>, John Niven
>([EMAIL PROTECTED]) wrote:
>> > (You have to own a license to watch TV in Britain? Fortunately I have a
>> > simple solution for that, having not watched TV at all for years... by
>> > choice.)
>
>> Not quite right - you have to own a license to own a TV. Subtle, but it
>> meant that the small colour set I had solely to use with my "micro-computer"
>> during the 80's required a license.
>
>Subtler than that. It's true that the legal test is not whether
>you operate the TV, but you don't have to have a licence to *own* a TV.
>You do have to have a licence to "install a receiving station".
>If you want to know what that means, hire a lawyer.
Well off topic now but here goes......uk.legal would be the place for
full clarification.
The actual offence is "TV licence payment evasion" and is covered
under the Wireless Telegraphy Act 1940 sect 1. I am fairly sure you
would have to be "operating" a TV set without a licence for a
prosecution to be worth while as I am led to understand that the
guideline sentence is a discharge or fine for the offence. HTH
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: NTRU, continued...
Date: Sat, 17 Mar 2001 11:42:02 -0000
Daniel Lieman <[EMAIL PROTECTED]> wrote in message
news:kMDs6.14766$[EMAIL PROTECTED]...
<SNIP>
> 5) I'd be more than happy to provide performance data to anyone -
comparing
> NTRU to ECC and RSA. We're quite pleased with the results.
I don't suppose you could put the results on a web page or post them here?
--
Regards,
Sam
http://www.scramdisk.clara.net/
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: qrpff-New DVD decryption code
Date: 17 Mar 2001 12:42:17 +0100
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> The problem with bringing up Nazis, is that *they* didn't believe
> that what they did was unethical or immoral. In fact, if you were to
> accept one single premise -- that anyone who isn't a male aryan isn't
> a person -- you would consider everything they did to be perfectly
> reasonable. Further, and possibly more importantly wrt your
> argument, the way they acted towards those who they *did* consider
> persons, was as moral and as ethical as you or I would act towards
> each other. The only thing that made them evil was their perception
> and treatment of non-aryans as non-persons.
So you're claiming that it's perfectly OK to torture a creature as
long as it's not a human?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Factoring RSA
Date: 17 Mar 2001 12:44:37 +0100
In article <[EMAIL PROTECTED]>, br <[EMAIL PROTECTED]> wrote:
> My idea is very simple : if you multiply every prime number P by X, P*X
> will be equal to 999999999999999999 ( (10^k) - 1) for k near the value
> n. You can prouve that in the neighbour of (10^n) - 1 (just few values
> of k), you will find P or Q.
Did you try computing (10^k)-1 for k equal to a 155-digit number?
How did you store the result? Hint: even if you were available to
store one Gigabyte into each and every single atom, all the atoms in
the entire universe wouldn't be enough to store that huge number....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Factoring RSA
Date: 17 Mar 2001 12:44:10 +0100
In article <[EMAIL PROTECTED]>, br <[EMAIL PROTECTED]> wrote:
> Try this algo to factor N.
> Let S= (10^k) - 1
> for k=N to (n/2) step -1
> Let c=gcd(S,N)
> if c<>1 or c<>N then c is a solution.
>
> It's hard to compute hudge number. But with computers able to manage a
> hudge number, it's feasible.
It's too slow. It's much slower than the standard naive algorithm:
for k=3 to sqrt(N) step 2
if (N % k) == 0 then k is a solution
and that too is far too slow for numbers having about 100 digits or more.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Computing power in the world
Date: 17 Mar 2001 12:46:18 +0100
In article <[EMAIL PROTECTED]>,
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> A MIPS-year is an useful metric for measuring the quantity of computation
> rather than the rate of computation. Factoring this composite, minimizing
> that sales route, or extracting a 3DES key from a plaintext/ciphertext
> pair are all tasks whose size might be measured in MIPS-years.
Trying to crack 3DES, or even 1DES, is preferably done on special
hardware implementing the DES algorithm: since DES was designed for
hardware implementations, this will be much faster (= several orders
of magnitude) than software implementations.
Now, if DES is executed on custom hardware rather than on some CPU,
it gets somewhat problematic to determine how many "instructions" a
DES execution requires. We can measure the time it takes, but not
how many "instructions" it takes - or one could argue it takes one
single instruction!
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Computing power in the world
Date: 17 Mar 2001 12:45:07 +0100
In article <[EMAIL PROTECTED]>,
Frank Gerlach <[EMAIL PROTECTED]> wrote:
> AirBete wrote:
>
>> Hi all,
>>
>> What is the up-to-date estimate of the total computing power in the world in
>> mips-years?
>
> MIPS-years are a silly metric.
> Its like asking "how many Megawatt-hours of processing capacity are there ?"
Actually, on my electric bills I et billed after the number of
kiloWatt-hours I've consumed.
But kilowatt-hours and megawatt-hours are no SI units. Instead one
should use Joules, kiloJoules, MegaJoules:
1 kiloWatt-hour = 3.6 Mega-Joules
1 MegaWatt-hour = 3.6 Giga-Joules
Likewise a MIP-year is 31.556952 Tera-instructions
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Computing power in the world
Date: 17 Mar 2001 12:43:42 +0100
In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]> wrote:
> Paul Schlyter wrote:
>> In article <[EMAIL PROTECTED]>, Darren New <[EMAIL PROTECTED]> wrote:
>>>> What is the up-to-date estimate of the total computing power in the world
>>>> in mips-years?
>>>
>>> mips-years would be mips * years, right? That doesn't sound like a useful
>>> measurement.
>>>
>>> MIPS by itself is the number of instructions you can execute in a given
>>> length of time. What does multiplying it by years get you?
>>
>> 1 MIP = 1 million instructions per second
>>
>> 1 MIP-year = numer of seconds in a year * 1 million instructions
>>
>> Thus:
>>
>> 1 MIP-year = 31556952000000 instructions = ca 3.15E+13 instructions
>
> But in what sense is this an estimate of computing power? Does it make sense
> to say "I have 3E13 instructions of computing power?" What happens when
> I've run 1E13 instructions? Do I now only have 2E13 instructions left? As I
> execute instructions, are they now dead? :-)
>
> (I realize my question of "what does multiplying it by years get you" is
> ambiguous. I meant it to be "why do you want to multiply by years?")
MIP-years is not a particularly useful measure of computing power,
but it could be a useful measure of the computer cycles consumed by a
particular program. So if you say "This program takes 1 MIP-year to
run", then it'll take one year on a 1 MIPS machine, 1 month on a 12
MIPS machine, 1 day on a 365 MIPS machine, or 10 years on a 100 kIPS
machine.
Compare with the measure man-month: "This project requires 100 man-months":
one man does it in 100 months, or 10 men does it in 10 months.
MIP-years probably scale better than man-months: "One man builds a
house in 3 months. How many men are needed to build the same house
in 5 minutes?". No-one expects a house to be built in 5 minutes, no matter
how many men you throw at the job. But if a program runs in 3 months
on a 1 MIPS computer, then one would expect it to run in 5 minutes on
a 26 GIPS computer.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Defining a cryptosystem as "broken"
Date: 17 Mar 2001 12:45:51 +0100
In article <[EMAIL PROTECTED]>,
Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote:
> Dann Corbit <[EMAIL PROTECTED]> wrote in message
> news:ifws6.141$xh6.657@client...
>> "br" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
>>> You wrote :
>>> "I can't say that I really understand how your algorithm works, since S
>>> does not change during the iterations. Perhaps I fail to understand
>>> some
>>> fundamental piece of the algorithm.
>>>
>>> Suppose as sample n=1633
>>> you have to try gcd( (10^1633)- 1,1633)
>>> gcd( (10^1632)-1,1633)
>>> etc... until S= (10^816) - 1
>>>
>>> Is it clear?
>>
>> What you are trying is clear now.
>>
>> Suppose we are trying to factor a mere 56 bit number. How long will your
>> algorithm take? For instance, suppose you are wondering about this
>> number:
>>
>> 72057594037927907 = 768467471 x 93767917
>
> Actually, by computing everything mod N, a single iteration of the above is
> actually feasible. However...
>
>> 10^72057594037927907-1 has a lot of bits! Do you have a computer at your
>> disposal that can hold this number?
>
> Far worse, he's cycling through 10^N-1 to 10^((N+1)/2) - 1. That's (N-1)/2,
> and since for a real problem, N will be a 1024 bit number, that's a *lot* of
> iterations. Unless you have some good reason that it's likely to find an
> answer in the first, say, 2**128 iterations or so, this doesn't look likely.
He won't even be able to complete the first iteration !!!!!!!!!!
10^(1024-bit number) will require a storage of some 2^1026 bits or
about 7E+308 bits. Now, since the universe "only" has about 1E+80
atoms, if each and every one of these atoms could be used to store
this number, one would still need to store about 1E+229 bits in each
atom! Now, 1E+229 bits is approximately one Tera-Tera-Tera-Tera-Tera-
Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-Tera-
bit. Where do we find the technology able to store this much
information in one single atom? And how do we integrate all atoms in
the universe into one integrated storage medium?
> Glancing at the math behind it, one would expect it to take O(q) iterations,
> where q is the size of the smaller factor. This isn't any better than trial
> division.
It's far worse than trial division, since trial division of N doesn't
require you to compute (10^N)-1 ...... In trial division he'll at least
be able to perform millions or billions of iteration within a reasonable
amount of time.
(btw that's the difference between math and computation: in math the
size of a number is no concern as long as it is finite; in computation
the size of a number DOES matter)
>> I don't think it is a good idea to use this method. I think it will be
>> impossibly slow on very easy problems.
...not to mention the impossibly large memory requirements, which
will grind that algorithm to a halt even on the very first iteration!
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: "Dobs" <[EMAIL PROTECTED]>
Subject: Re: primes for Blum Blum Shub generator
Date: Sat, 17 Mar 2001 13:27:31 +0100
I'm sorry I'm so boring ::)))))))))) but I must be blind ..or something. I
am looking for BN_generate_prime for 2-3 hourse and I can not find it
::((((( If it is not in bn_prime.c, bn_prime.h, bn.h and many others so
where could it be. I can see that BN_generate_prime function is used very
often , but I cannot find the function itself( where I can find source code
of this function and and find out how its working)
Perhaps I have no this files, I downloaded the openssl-0.9.2b version, maybe
it is not there
Thanx
> Oops. My typo. That should have been:
> while(NOT(isPrime(R))
> My mistake. I apologize. That'll teach me to type faster than I can read.
>
> The function to look for in openssl is BN_generate_prime. The
documentation
> on it is at http://www.openssl.org/docs/crypto/BN_generate_prime.html
> Joe
>
> "Dobs" <[EMAIL PROTECTED]> wrote in message news:98tn8e$aqv$[EMAIL PROTECTED]...
> > Thanks for help :))))
> > U mean that I have to choose randomly big number choose it if it is odd
> and
> > then choose if it is prime. If not add 2 to this number and choose it
one
> > more time if it is prime, right? I do not know what is function
israndom,
> I
> > think that U meant isprime( that I have to choose if it is prime) I can
> not
> > see any point to check if it is random?
> >
> > U wrote that I can use to prime number generator from openssl, I
download
> > this openssl file, but there are so many directories, files , I can not
> find
> > it and I think if I found it it would be integrated with others
libraries
> > like *.h, and I could not use it because I am not so good at programing
to
> > make it work in my program.Perhaps U know any different source where I
can
> > find easier prime number generator or algorithm to it
>
>
>
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: IP
Date: Sat, 17 Mar 2001 13:57:06 -0000
<[EMAIL PROTECTED]> divulged:
>Other dumb questions: If an ISP having a large number of
>customers very efficiently assigns different dynamic IPs
>to its customers at different time points, wouldn't that
>contribute substantially to anonymity (i.e. the
>functionality of anonymizers)? Would it be possible
>for the ISP even to change the assignment of IPs during
>the connection time of the customers so that better
>anonymity is achieved? Thanks.
no, because most of what you do that compromises your privacy and security
is what you do, not where you are. and not generally, because the ppp
protocol can't really handle it and even if you were using something that
could handle making a change (e.g., dsl with dhcp) it would destroy all
current connections which would be a customer service nightmare.
if you don't mind my saying, this is more a security or privacy kind of
discussion ...
--
okay, have a sig then
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: Q: IP
Date: Sat, 17 Mar 2001 13:58:28 -0000
<[EMAIL PROTECTED]> divulged:
[re an isp using nat on customer connections]
>A company that did that would not be providing Internet access.
and yet several companies do, e.g., bell atlantic's adsl service.
--
okay, have a sig then
------------------------------
** 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
******************************
