Cryptography-Digest Digest #286, Volume #9 Thu, 25 Mar 99 18:13:03 EST
Contents:
Re: RSA Algorithm (STL137)
Re: Random Walk (karl malbrain)
CFP: International Workshop on ELECTRONIC COMMERCE (WELCOM'99) (Sebastian Staamann)
Re: Random Walk (karl malbrain)
Re: compare RSA and D-Hellman (DJohn37050)
Re: RSA key distribution (DJohn37050)
Re: Randomness based consciousness?. (Was: Re: *** Where Does The (Igor Podlesny)
Re: Random Walk (Dave Knapp)
Re: Random Walk (R. Knauer)
Re: RSA Algorithm (DJohn37050)
Re: Randomness based consciousness?. (Was: Re: *** Where Does The Randomness Come
From ?!? *** ) (R. Knauer)
Re: RSA Algorithm (Michael Sierchio)
Re: RSA key distribution (Peter Smith)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (STL137)
Subject: Re: RSA Algorithm
Date: 25 Mar 1999 20:13:25 GMT
This is a reply to three separate posts by different people.
<<Well, checking only eleven pairs, and picking one isn't going to be much
worse
than picking one pair at random. However, extremely low private exponents are
known to be weak, so you probably don't want to do this with a billion pairs.>>
I'm running this on a calculator - I can't afford to do much more than eleven
pairs.
<<(Also, if you are looking at minimizing decryption time, why don't you take
the
S that require the least number of multiplies, rather than the strictly
smallest
one)>>
I'll see if I can hack this in. Good point. I.E. look for the S with the least
amount of "1"s in its binary form, right?
<<Bad idea, for several reasons:
[Regarding my method of chunking text into blocks started with a random
number]>>
<<- Two identical passages have a 10% probability of being encrypted the same
way. This can easily happen if you are encoding boilerplate text, or one
message quotes the other. This leaks a lot of information about the
plaintext. For example, if the attacker has the plaintext to one of the
messages, he then has part of the plaintext to the other. At the very
least, the attacker will realize that the two messages are related.>>
Good point. I don't think it would be 10% with quoting (the blocks would have
to line up EXACTLY, a rare occurence when each block captures, say, 50 decimal
digits). But it's hard to find a way around this...
<<- It makes it easy for an attacker to verify whether a particular plaintext
corresponds to a particular ciphertext -- all he needs to do is encrypt
the plaintext with the 9 possible random numbers before every chunk.>>
No matter what I do with RSA, that's a problem. The random digit isn't there to
stop this attack: it's so that ASCII codes that start with zero (say a chunk
looks like 003231187...) don't get the leading zeros chopped off by the
calculator.
<<- This is a lot slower than it needs to be (more than 100x slower on long
messages). Typically, what people do in this situation is pick a 'session
key', encrypt the session key using RSA, and send that, along with the
plaintext encrypted using a symmetric cipher (eg. DES or blowfish) using
the session key. Unless your message is only one or two chunks, the
greater speed of the symmetric cipher more than makes up for the
additional complexity.>>
Of course. But I don't know of any symmetric algorithms I can easily implement
on a *calculator*. The most these keys can be is N=250digits, or so.
<<AMEN! Don't EVER use a private exponent that is less than N^(.29) where N
is the public modulus.
It is conjectured that .29 should be replaced with .5, but we have no proof
as yet.>>
Got a source on this? If the private exponent is less than sqrt(N) or N^.29,
does a brute-force looking for the private exponent do better than factoring? I
will set my program to look for this.
<<Usually the public exponent is "common" and small -- and usually a
Fermat prime, i.e. 3, 17 or 65537. This assures that the private
exponent is large, too.>>
The eleven public exponents I look at are a few Mersenne primes and a few
10-digit random primes (prechosen and hardcoded into the program). How small
should "small" be? For now I'll remove the primes over 5 digits I have there
and put in a few Fermat primes. (Wow - Fermat primes are nice to encrypt to -
that HAS to be why they're used).
*****
So, I have further questions:
Do you have any suggestions as to how I could still use RSA yet avoid this
nagging problem of chunking? I really, really don't want to have to turn to a
symmetric algorithm, especially one that requires me to do bit fiddling.
If I look at a dozen or so public-private exponent pairs, choose the public
exponents from Fermat primes, 5 digit primes, and the very lowest number that
will work, and make sure the private exponent isn't less than sqrt(N), is that
okay?
Should I put in Mersenne primes to look through for the public exponent? They,
for their size, are the very worst to encrypt to, but they might make the
(much, MUCH) slower process of decryption faster.
-*---*-------
S.T.L. ==> [EMAIL PROTECTED] <== My quotes page is at: http://quote.cjb.net
~~~ My main website is at: http://137.tsx.org ~~~
If you see a message of mine posted on two newsgroups, then it is because I
have replied to a crossposted message. I *never* crosspost of my own accord!
I block all unapproved E-mail. If you wish to talk to me, post to alt.test.9
with the subject "Moo" and your E-mail address in the body. I will allow you
as soon as I sign on next.
"This universe is not hostile, or yet is it friendly. It is simply
indifferent" - John H. Holmes, The Sensible Man's View of Religion
------------------------------
From: karl malbrain <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 20:11:07 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> The Looneytarians want all drug laws repealed based on the observation
> that most people can function in society in a safe manner while under
> the influence of certain drugs, even those considered "hard core" like
> heroin and cocaine. And they are correct in that assessment - most
> people can indeed function in society when using most drugs.
>
I think you've gotten this wrong. The Libertarians seem to be saying: it
costs society more to prosecute and incarcerate people on DRUG laws than the
damage done by individuals to themselves and society.
Again, they've got that wrong. The real MOTIVE here is to build a
BOURGEONING INMATE POPULATION to work for private corporations in a can't
lose setting. Never mind that we just chastized CHINA for doing the exact
same thing (placing into commerce inmate produced goods & services). Karl M
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Sebastian Staamann)
Subject: CFP: International Workshop on ELECTRONIC COMMERCE (WELCOM'99)
Date: 25 Mar 1999 20:53:28 GMT
Call for Papers
International Workshop on
ELECTRONIC COMMERCE
October 18, 1999
Swiss Federal Institute of Technology
Lausanne, Switzerland
In Conjunction with the:
18th IEEE International Symposium on Reliable Distributed Systems
http://lsewww.epfl.ch/Events/srds99/welcom/
------------------------------------------------------------------------
SCOPE
Electronic commerce is becoming one of the most important fields of usage
and at the same time one of the driving forces behind the fast development
of the Internet. E-commerce is expected to have a strong impact on how
business will be conducted in the near future. Thus, the interest in this
topic of research as well as in product and service development is immense.
However, the more successful the idea becomes, the more we see the need for
discussion and clarification of the generic technical building blocks to
create e-commerce services and of the business models that underlie the
technical concepts.
The goal of this workshop is to bring together researchers and practitioners
to discuss the development of technical concepts, products, and
infrastructures for electronic commerce services. A main topic will be the
discussion of base technologies for various application scenarios of
e-commerce applications. The focus is here on the differentiation between
e-commerce services provided to residential customers and e-commerce service
for business-to-business interactions (extranets). In particular, we
encourage the discussion of security and reliability issues of new
technologies for the latter case.
The goal of this workshop is to provide a forum to meet and discuss the
technical and technology related issues related to e-commerce. Suggested
topics for research and position papers include, but are not limited to:
* experiences with practical realisations of e-commerce applications in
an industrial environment
* analysis of and differentiation between various types of e-commerce
services
* innovative technologies for and special aspects of business-to-business
interactions
* security aspects of e-commerce service provision
* privacy aspects of e-commerce service interactions
* the role of trust for e-commerce service provision
* reliability aspects of e-commerce service interactions
* high availability of e-commerce services
* service creation environments for e-commerce services
* the use of middleware for the realisation of e-commerce services
* the role and usage of component based concepts for e-commerce
The program of the workshop will consist of a set of paper presentations and
discussions. The papers will be published by the IEEE Computer Society
press.
IMPORTANT DATES
Papers due:
May 15, 1999
Notification of acceptance:
June 18, 1999
Final papers due:
July 16, 1999
Conference date:
October 18, 1999
LOCATION
Swiss Federal Institute of Technology, Lausanne, Switzerland.
AUTHOR INFORMATION
Authors are invited to submit papers according to the following submission
guidelines:
The papers must not exceed 6 pages. They should be formatted according to
the IEEE format: double column, single space, 10 point Times font. Please
consult the IEEE author guidelines at
http://www.computer.org/author/author.htm for details.
Submissions should be made electronically in PDF or postcript (no hardcopy)
and sent to [EMAIL PROTECTED] Detailed instructions about the submission
procedure are available at
http://lsewww.epfl.ch/Events/srds99/submission.html. If you have any
question, you can contact us at [EMAIL PROTECTED]
WORKSHOP CO-CHAIRS
Sebastian Staamann
Swiss Federal Institute of Technology, Switzerland.
Uwe Wilhelm
Swiss Federal Institute of Technology, Switzerland.
------------------------------
From: karl malbrain <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 19:47:17 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "R. Knauer" wrote:
> > I used to believe what you are saying but have modified my position. I
> > no longer believe that algorithmic tests can tell you anything
> > *definitive* about the "non-randomness" of a process which generates
> > finite sequences. The reason is that there is no a priori measure of
> > what constitutes either randomness or non-randomness for finite
> > sequences. The matter is indeterminate on either side of the truth
> > table.
>
> I don't know what "truth table" is involved here, but I think I see
> one thing at least that has misled you. It is not that a single,
> finite output of the process is tested for (non)randomness, but
> rather that the likelihood of the hypothesis that the process is
> random is evaluated based on the observed output.
The truth table is INFORMATION under DETERMINISM
(DEGREES DETERMINED/INFORMATION ACCUMULATED).
The very nature of USENET and the WEB is that INFORMATION is FREE OF CHARGE.
One just GIVES the program away (or shares it under nominal fee) so you can
STEP BACK and let more INFORMATION ROLL IN!!!
Yes, I concur, R Knauer is being confused by FASCISM under SOCIAL DEMOCRACY,
which holds ALL INFORMATION (input or output) MUST BE DETERMINED as
prerequisite to the ability to GROUND CHAOS as a force. (fascists in Italy
made the trains run on time again, and fascists in Germany NULLED out the
unbearable Versailles Treaty reparation, and you know the rest).
Karl M
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: compare RSA and D-Hellman
Date: 25 Mar 1999 21:15:31 GMT
See IEEE P1363. It is best if g does not generate A but generates a prime
order subgroup. Pohlig Hellman says that this is what dominates the strength
formula anyway.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: RSA key distribution
Date: 25 Mar 1999 21:21:32 GMT
Roger,
It is not true that Bob's procedure MUST be used. ANSI carefully separated the
requirements from the recommendations from the examples. Bob's method is one
method and in some sense shows that the requirements could be met in a
reasonable way without too much performance cost. But it is not THE required
method, others are possible as long as the requiements are met.
Don Johnson
------------------------------
From: Igor Podlesny <[EMAIL PROTECTED]>
Crossposted-To:
sci.skeptic,sci.philosophy.meta,sci.psychology.theory,alt.hypnosis,sci.logic
Subject: Re: Randomness based consciousness?. (Was: Re: *** Where Does The
Date: Fri, 26 Mar 1999 01:34:34 +0700
Reply-To: [EMAIL PROTECTED]
"james d. hunter" wrote:
> Seisei Yamaguchi wrote:
> >
> > Hi, this is Seisei.
> >
> > In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] wrote:
> >
> > >I don't know where this idea of Random based conscioussness comes
> > >from, Random Consciousness is an oxymoron...
> >
> > You are right. And I wrote {
> >
> > If the link ---adaptive network--- pattern of the brain cells
> > (include pattern generating routine (distributed system) )
> > is TRUE RANDOM,
> >
> > it means our consciousness
> > ---cells network organized from astronomical number of
> > pulses come from the interface and self feedback system---
> > is controled by TRUE RANDOMNESS.
> > }.
>
> That has to be a priori wrong.
> It is impossible for TRUE RANDOMNESS to CONTROL *anything*.
If the world is built on random base how do we control anything?
-- in incomplete way. Nobody can control everything. (let's skip
religion) If such property as random belongs to the whole thing it belongs
to
its parts and vice versa.
>
>
> TRUE RANDOMNESS is simply the universe's way of propagating
and nobody knows wether our world is built on randomness.
>
> weird theories of randomness. Nothing more, nothing less.
>
> ---
> Jim
------------------------------
From: Dave Knapp <[EMAIL PROTECTED]>
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 21:53:50 GMT
"R. Knauer" wrote:
>
> On Tue, 23 Mar 1999 23:24:32 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
>
> >It is hard to judge a citation out of context, but certainly
> >this does not contradict what Trevor said (which is correct).
>
> Then read the book. When you have, come back and tell us your opinion.
Geez, you've got a lot of gall. You refuse to read even the most basic
book on statistics, but presume that your understanding of Kolmogorov is
perfect and that everyone should bow down to it, despite your daily
demonstration that you have NO understanding of statistics or
probability.
I wonder why nobody takes you seriously?
-- Dave
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: Random Walk
Date: Thu, 25 Mar 1999 21:56:15 GMT
Reply-To: [EMAIL PROTECTED]
On Thu, 25 Mar 1999 14:26:20 -0600, Jim Felling
<[EMAIL PROTECTED]> wrote:
>> Who says that lack of bias is a property of finite true random
>> sequences? Where is that proven in a mathematics book?
>It is not necessarily a property of truly random sequences -- however if my
>seemingly perfect and diagnostically checked generator is producing output with a
>(to use a very poor example) 60% 1's and 40% 0's and has done so since time T and
>continues to do so.
Continues to do so for how long?
>I am then vulnerable to attacks on my OTP thus generated --
>despite the fact that what I am using is a TRNG.
Not so. If you are using a TRNG, then there will be nothing to lead
the cryptanalyst to conclude that a long run has occured. He will see
plaintext that is clear if you use a simple mixing scheme like XOR,
but that is assumed not to be the case. It is assumed that at least
you compressed the plaintext so it will not look clear if there is a
run of zeros.
But even if the text is clear, that does not give the cryptanalyst any
reason to believe that the underlying keystream consists of a run of
zeros.
>(however, this is highly
>unlikely to occur in a properly working system and would probably get the system
>shut down as my guess is that it would fail 2X or 3X and be removed for
>reconditioning as the probability that it is properly functioning would be lower
>than the probability that I made a mistake in my diagnosis and missed something.
I would treat the occurance of a long run as a diagnostic warning and
check the TRNG.
>Yes this results in the selective culling of certain long sequences (20000+ bits
>in length) occurring, however I feel that the "bias" that this will contribute is
>better than having my data vulnerable to a whilst unfounded, none the less working
>attack. In addition I feel that this will result in a cull occurring 1X in the
>time it takes to generate 2^10000 bits -- a fair tradeoff in my mind.
I agree with you in practice, even though it is incorrect in
principle. But the greater likelihood is that a run was caused by a
malfuncting TRNG, in which case you are correct to discard the run.
>> Let me ask you a crucial question. You buffer a 10,000 bit sequence
>> and submit it to statistical testing before outputing it, so you can
>> prevent a broken TRNG from creating a bad keystream. You get a
>> diagnostic warning and shut the TRNG down for further tests. You find
>> that the TRNG is not broken - that the original tests have given a
>> false indication.
>If I were administering that system such a generator would trip a flag. I would
>buffer and test further. If the RNG is revealed to be unflawed I would then
>release the buffered bits.
Would you do that for a long run too? If not, as you stated above, why
not - since a long run is just as likely as any other sequence,
including one that tripped the flag above.
Bob Knauer
"Outside of the killings, Washington D.C. has one of the lowest
crime rates in the country".
-- Marion Barry, Mayor of Washington D.C.
------------------------------
From: [EMAIL PROTECTED] (DJohn37050)
Subject: Re: RSA Algorithm
Date: 25 Mar 1999 21:18:05 GMT
Dan Boneh has a paper on his web page about d being weak if smaller tan .282 n
or some such. He thinks the real number is .5.
Don Johnson
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Crossposted-To:
sci.skeptic,sci.philosophy.meta,sci.psychology.theory,alt.hypnosis,sci.logic
Subject: Re: Randomness based consciousness?. (Was: Re: *** Where Does The
Randomness Come From ?!? *** )
Date: Thu, 25 Mar 1999 22:12:58 GMT
Reply-To: [EMAIL PROTECTED]
On Fri, 26 Mar 1999 01:34:34 +0700, Igor Podlesny <[EMAIL PROTECTED]>
wrote:
>If the world is built on random base how do we control anything?
Because some things are ordered, even though they are random. You are
confusing complexity with true randomness.
For example, the run of 10 straight zeros is one of the possible
sequences of flipping a coin 10 times. It has the same chance of
occuring as all the other ( (2^10) - 1 ) sequences. Therefore the
process that generated it, namely the flipping of a fair coin, is
random, even though the sequence of all zeros is highly regular.
Since regular sequences are economical in terms of algorithmic
complexity, they are preferred by nature. The planets obey Newton's
Laws because Newton's Laws are an expression of the economy of the
planetary motion we see.
There is a theory called Fisher Information which goes even farther
than that. The book "Physics from Fisher Information : A Unification"
by B. Roy Frieden hasn't hit the libraries quite yet since it was just
published in February 1999. The theory claims is based on the
"principle of information extremization". This is the blurb from
amazon.com:
+++++
The principle states that when knowledge is sought by a person, the
act of seeking creates for that observer the physical law that gives
rise to the knowledge. For example, in making a measurement of
position, the observer locally creates quantum mechanics--the physical
law that gives rise to such a measurement. In this way, man creates
his own local reality. For observations that do not involve time
directly, the act of seeking such knowledge amounts to a game
of information hoarding between the observer and nature. The payoff of
the game is the law of physics in question.
+++++
At first glance that sounds a lot like the tenents of Phenomenology,
but I am going to reserve judgement until I read the book.
>If such property as random belongs to the whole thing it belongs to
>its parts and vice versa.
So?
>and nobody knows whether our world is built on randomness.
Quantum Mechanics tells us that the physical world is most defintitely
built on randomness. If you can come up with a system to replace QM,
then by all means let us know about it.
After nearly a century of the brightest minds trying to find a hidden
variable theory to replace QM, they have come up emptyhanded.
I leave you with this quote:
+++++
"If you want to build a robust universe, one that will never go wrong,
then you dosn't want to build it like a clock, for the smallest bit of
grit will cause it to go awry. However, if things at the base are
utterly random, nothing can make them more disordered. Complete
randomness at the heart of things is the most stable situation
imaginable - a divinely clever way to build a universe."
-- Heinz Pagels
+++++
Bob Knauer
"Outside of the killings, Washington D.C. has one of the lowest
crime rates in the country".
-- Marion Barry, Mayor of Washington D.C.
------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: RSA Algorithm
Date: Thu, 25 Mar 1999 14:34:38 -0800
Reply-To: [EMAIL PROTECTED]
DJohn37050 wrote:
>
> Dan Boneh has a paper on his web page about d being weak if smaller tan .282 n
> or some such. He thinks the real number is .5.
> Don Johnson
Cryptanalysis of RSA with d less than N**0.292
D. Boneh and G. Durfee
http://theory.stanford.edu/~dabo/abstracts/lowRSAexp.html
------------------------------
From: Peter Smith <[EMAIL PROTECTED]>
Subject: Re: RSA key distribution
Date: Fri, 26 Mar 1999 10:48:34 +1200
Reply-To: [EMAIL PROTECTED]
Roger Schlafly wrote:
>
> DJohn37050 wrote in message <[EMAIL PROTECTED]>...
> >As Bob said, the bankers chose to exclude the possibility of certain
> classes of
> >attacks, at a small cost, rather then allow a very small chance that they
> would
> >work.
>
> This is a completely useless thing to be doing as long as there are
> other attacks which are much more likely to succeed.
>
EXCISION
> > This was a conservative choice that they should be allowed to make.
>
> It is not just a banking standard. It is an ANSI standard, and soon to
> become
> a US govt standard. There is a proposed FIPS that rubber-stamps the
> ANSI standard.
>
> It is reasonable to say that the bankers should be able to generate their
> own keys using criteria that they believe to maximize security. However,
> the standard does not allow this. Everyone must use bobs's procedure
> even though most experts (including bobs?) disavow it as misguided.
The question with 'strong' primes is: Where does one stop? The (P+1,
P-1) guards add structure to P, which may make it more easily guessed.
The (P-1) attack can also be extended, as the following shows. This
simple attack would seem to require yet more structure to be added to P.
Take P = 103 = 2.3.17 + 1. Starting with 7, repeatedly square values
modulo P to produce a cycle: 7, 49, 32, 97, 36, 60, 98, 25, 7, 49,..
which repeats after eight squarings. As another example, take P = 179 =
2,89 + 1, and start with 5, producing: 5, 25, 88, 47, 61, 141, 12, 144,
151, 68, 149, 5, 25,... which repeats after eleven squarings.
It is easy to see that the length of the cycle depends on the
twice-iterated Euler 'phi' function. phi(103) = 2.3.17, phi(2.3.17) =
2^5 = 4.8; phi(179) = 2.89, phi(2.89) = 2^3.11.
Algorithms based on this idea are not general purpose, since they have a
worst case of about P/4 steps, but are very effective when phi^2(P) is
small.
It is possible to extend this to thrice-iterated phi, but the process
quickly runs out of steam, since the number of steps is the square of
the previous number of steps. For example, if P = 23, then first
squaring, then raising to 4th, then 16th, 256th, 65536th powers produces
a sequence like: 7, 3, 12, 18, 13, 3, 12, ... with a cycle length of
four. phi^3(23) = 2^2
Using Lucas functions it is possible to extend this idea to (P+1) as
well.
Peter Smith
L U C E N T
Visit our website http://www.luc.co.nz
------------------------------
** 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
******************************
