Cryptography-Digest Digest #717, Volume #10 Fri, 10 Dec 99 10:13:01 EST
Contents:
Re: symmetric encryption based on integer factoring (Tom St Denis)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: symmetric encryption based on integer factoring ([EMAIL PROTECTED])
Re: weak algorithm, too hard for me (Guy Macon)
Re: If you're in Australia, the government has the ability to modify ("Trevor
Jackson, III")
Re: Digitally signing an article in a paper journal ("Trevor Jackson, III")
Re: Synchronised random number generation for one-time pads ("Trevor Jackson, III")
Re: Random Noise Encryption Buffs (Look Here) ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: symmetric encryption based on integer factoring
Date: Fri, 10 Dec 1999 13:00:06 GMT
In article <82q3tn$s27$[EMAIL PROTECTED]>,
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> This problem appears to have nothing to do with "factoring". It's
> strength, if any, looks like it be closer to the discrete log problem.
> Also, the multiplicative inverse of a generator is always a generator,
> so there's no need to specify it directly.
Oh ok.
> Well, lets make a preliminary analysis of it. I assume that g and p
are
> publicly known parameters. Since you do not describe how x is
generated,
> let us assume that all possible values of 0 <= x < p-1 are equally
probable.
> Then, we immediately note that all values of g^x from 1 <= g^x < p are
> equally probable, since because g is a generator, there is a one-to-
one
> mapping between the two. So, your system could be simplified to:
>
> C = (P * y) mod p
> P = (C * y^-1) mod p
>
> Where all values 1 <= y < p are possible. Next, we note that, for any
> possible pair P, C, there is a unique y s.t.
>
> C = (P * y) mod p.
>
> In other words, for any C, for each possible plaintext P, there is a
> key that will decrypt it to that plaintext. This implies that this
> system is essentially an OTP, except it's a lot harder to evaluate.
>
> And so, *all* the strength of the system is in how you generate x.
Yes and no. There is a reason why I chose g^x mod p, instead of just x.
> Essentially. Assume the attacker has the plaintext/ciphertext for the
> first message. Then, he can compute:
>
> g**X = C * P**-1 mod p
>
> Then, given the nth ciphertext Cn, he can compute
>
> Pn = Cn * (g**X)**-n
> = Cn * (g**-nX)
>
> I believe any linear method of assigning x's will have the same
problem.
That's what I thought. Originally I said why not just increment x mod
p-1. But I then proceded to break it ... :)
> >Just an idea :)
>
> BTW: why do you think that this is even slightly practical? You
require
> a full modular exponentiation for every single message. You can run
> RSA just as fast.
It's not, but I am toying with number theory. They don't teach it in
school so I have to work it out myself, and ask here once in a while.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Synchronised random number generation for one-time pads
Date: 10 Dec 1999 08:17:09 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tim Tyler) wrote:
>OTPs are generally quite secure against eavsdroppers who don't know the
>message they contain. They're useless against simple complete
>known-plaintext attacks.
It depends on what you mean by "useless". I would say that being able
to send other plaintexts without the attacker being able to decode
them is quite usefull, wouldn't you? The known-plaintext attack
described does allow interception and substitution, which is another
way of saying that an OTP has limited value as a digital signature.
The known-plaintext attack never allows the attacker to do anything
with a message other than his known-plaintext message. That's useful.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Synchronised random number generation for one-time pads
Date: 10 Dec 1999 08:25:41 EST
In article <82pet6$cob$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Charles Meigh) wrote:
>
>Thanks everyone, I hadn't come across the problem of interception and
>forgery yet. I think I'll add a decent physics textbook to my shopping
>list as well as cryptology. I'm still thinking that there might be some
>vastly wide choice of 'celestial' events that could produce truly random
>numbers that will still be sufficiently similar observed from any two (or
>more) points on the globe, which would make OTP use more economical.
You have that already. Just generate your random numbers using whatever
method you prefer and post them in a newsgroup. Or you can put them on
a CD and sell the CD on a web site. Or broadcast them with a ham radio.
Getting your random numbers to two or more points on the globe is trivial.
What is hard is getting your random numbers to exactly two (and no more
than two) points on the globe and not to any other points on the globe.
Alas, the latter is what you need if you want to have the shared secret
that is the basis of OTP encryption.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Synchronised random number generation for one-time pads
Date: 10 Dec 1999 08:36:44 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Trevor Jackson, III) wrote:
>Encrypting a message with an OTP does not provide 100% security in the sense
>of 0% chance the opponent will learn the plaintext. I.e, the cipertext does
>not forbid an opponent from thinking of the plaintext. The opponent would
>always generate his own keystream and be right as often as 2^(-MsgLen).
>That's not zero. But it is as practically close to zero as any reasonable
>authentication scheme will get you. Below (say) 2^(-256) all numbers have the
>same practical importance -- none.
No. Even if the opponent is very lucky and guesses the entire random
string that goes into the OTP, he STILL hasn't learned the plaintext.
Even if he does a complete set of all possible guesses, he STILL hasn't
learned the plaintext. All he has is a list of all possible plaintexts
of theat length, including selections from Shakespear, Speeches by Al
Gore, this post, and near misses with a word or a phrase changed. He
has no way of knowing which is real. Absolute protection against
cryptoanalysis by someone with infinite computer resources, infinite
skills, and infinite knowledge of everything is the universe except
for the random key and the plaintext.
Is there an authentification method that provides this level of security?
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: symmetric encryption based on integer factoring
Date: Fri, 10 Dec 1999 13:25:26 GMT
In article <82oub7$dg2$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I was plumbing around with the idea of a cryptosystem based around
> factoring such as
>
> C = (P * g^x) mod p
> P = (C * g^-x) mod p
This looks very much like El-Gamal except to decrypt a message you use
division, not an inverse of g^x. Essentially, you have a Discrete
Logarithm Problem and you're implementing decryption in a different
manner. However, it may become an interesting alternative for public
key encryption since it appears you don't have to send as much
information as you do when using El-Gamal. Did you figure out a way to
create g^-x?
csybrandy
>
> Where given the ciphertext you have to factor it to determine what the
> plaintext could be [as long as p is prime, and g is a generator, and
> that the mult. inverse of g is a gen as well]. Each message would
> have their own 'x' derived somehow [RNG?]
>
> I then proceded to brutally assalt it. I made an attack using one
> known plaintext if you re-use 'x' or use 'x' values close together [by
> exploiting the base].
>
> So then I ask what would be a good method of choosing new 'x' values
> per message? I was thinking of making x odd, then X=x, x' = x + X, so
> the gap between successive X values is not known. Could the same
> attack exploit it?
>
> Just an idea :)
>
> I would love feedback.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: weak algorithm, too hard for me
Date: 10 Dec 1999 08:40:08 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(JPeschel) wrote:
>Gee, it's not that tough, guy!
>I already gave him the password.
Your a smart fellow. You can figure this one out. :)
(Hint: Usenet article propagation times: constant or variable?)
------------------------------
Date: Fri, 10 Dec 1999 09:12:47 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: If you're in Australia, the government has the ability to modify
Douglas A. Gwyn wrote:
> "Trevor Jackson, III" wrote:
> > I thought so too. Then I reied to install the latest Microsoft(tm) tools.
> > Visual C now refuses to install unless Internet Explorer is present. I am
> > unable to conceive of a legitimate reason for such "persuasive" market
> > positioning.
>
> That is simply the result of Visual Studio's help system having
> been changed to HTML rather than Microsoft's old proprietary
> format. Looks like progress to me.
I doubt it. I have a perfectly adequate HTML renderer installed -- a
non-Microsoft(tm) browser. If, as you suggest, this issue is only HTML
handling, the product would not care who/what/where/how/why the HTML was
handled, only that an association between HTML and a handling program existed.
That is not the case AFAICT.
------------------------------
Date: Fri, 10 Dec 1999 09:40:30 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Digitally signing an article in a paper journal
KloroX wrote:
> On Fri, 10 Dec 1999 01:40:23 -0500, "Trevor Jackson, III"
> <[EMAIL PROTECTED]> wrote:
>
> >Several questions:
> > 1. What is at stake?
> > 2. Who are the opponent? What is your threat model?
>
> I answered a similar question earlier in the thread, before seeing
> your post. You may read about the background there. The threat could
> be losing my job (in the worst case), or be subjected to career or
> financial reprimands.
> >Suggestions:
> [...]
> > Give the unopened manuscript envelope to a lawyer you trust.
>
> Anyone who knows a lawyer he can trust raise his hand...
> Seriously, what is the advantage of the multiple-hash scheme? Making
> it less likely that a collision will be found (i.e., another plaintext
> that yields the same hash), or facilitating verification (increasing
> the likelihood that at least one of several hash algorithms will still
> be easily available after several years)?
The only purpose of multiple signatures/hashes is to insure the long-term
authenticity of your signature. If you expect to uncover the ruse in the
short term, say <5 years, a single authenication may suffice. But if you
want decades of security, a single scheme is vulnerable to catastrophic
collapse in the face of a critical advance in the state of the art. If an
advance in the state of the art weakens the signature technique you use
your ability to prove your authorship will be equally weakened. Two (or
three) independent signatures squares (or cubes) that small risk.
As for lawyers, there's a difference between trusting their judgement (not
ever) and trusting their integrity (usually). How do you pick a
trustworthy banker, doctor, spouse? Abstract trust: "the emotional
residue of past agreements". Practical trust: "the condition necessary
for betrayal".
------------------------------
Date: Fri, 10 Dec 1999 09:59:49 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Synchronised random number generation for one-time pads
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Trevor Jackson, III)
>wrote:
>
> >Encrypting a message with an OTP does not provide 100% security in the sense
> >of 0% chance the opponent will learn the plaintext. I.e, the cipertext does
> >not forbid an opponent from thinking of the plaintext. The opponent would
> >always generate his own keystream and be right as often as 2^(-MsgLen).
> >That's not zero. But it is as practically close to zero as any reasonable
> >authentication scheme will get you. Below (say) 2^(-256) all numbers have the
> >same practical importance -- none.
>
> No. Even if the opponent is very lucky and guesses the entire random
> string that goes into the OTP, he STILL hasn't learned the plaintext.
> Even if he does a complete set of all possible guesses, he STILL hasn't
> learned the plaintext. All he has is a list of all possible plaintexts
> of theat length, including selections from Shakespear, Speeches by Al
> Gore, this post, and near misses with a word or a phrase changed. He
> has no way of knowing which is real. Absolute protection against
> cryptoanalysis by someone with infinite computer resources, infinite
> skills, and infinite knowledge of everything is the universe except
> for the random key and the plaintext.
>
> Is there an authentification method that provides this level of security?
OK, the original complaint was that authentication does not have the same "100%ness"
of an
OTP. Let's define 100%.
The maximal strength of an OTP derives from the mapping of plaintexts onto ciphertexts.
There is no constraint on the mapping other than message length. The 100% means all
possible mappings.
A similar mapping occurs between text and signature. A signature that can be derived
from
only a subset of the possible texts is not "100%" in the sense used by the original
poster. So the "level of security" you referred to is only available for signatures
that
occupy 100% of the signature space (assuming the signatures are smaller than the
texts).
Such a scheme was presented a few days ago. The sender uses a randomly generated
secret
that is shared with the receiver. This satisfies the "100%ness" criteria because the
random generation insures that any signature could apply to any message. The receiver
knows that only the sender posessed the secret.
This technique lacks the convenience of deterministic hashes, but provides the level of
security you specified.
------------------------------
Date: Fri, 10 Dec 1999 10:05:30 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Random Noise Encryption Buffs (Look Here)
Guy Macon wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Tony T.
>Warnock) wrote:
>
> >The main point is that in designing a radioactive decay counter, the dead
> >time of the detector (or it's altered state), that is, the time right after
> >a hit, will be a time which gets lots of decays. An interval of the dead
> >time, T, which starts at a hit is more likely to get a hit than the same
> >interval delayed to after the dead time. It only makes the design a bit
> >more complicated.
>
> If I understand you correctly, you are saying that an individual
> Radium atom is more likely to decay into a Radon + Alpha particle
> if another Radium atom just did. This can't be correct - I must
> be misunderstanding your meaning. Each "hit" is a radium atom
> decaying in a sample that has many, many atoms. How does an
> individual radium atom "know" that an atom on the other side of
> the sample just decayed? I can see how an isotope that decays
> to neutrons could cause a chain reaction (amount of bias would
> depend on how close to critical mass the sample is) but I the
> decay of radium atoms only puts out alpha particles, which
> don't cause nuclear chain reactions.
>
> Here are a couple of chunks I pulled from some web sites.
>
> "The most abundant isotope of Radium is Radium 226, which
> decays into Radon plus alpha particles with a half-life
> of 1620 years."
>
> "The emission of radioactivity by an atom occurs spontaneously
> and quite unpredictably. However, in a sample containing
> many radioactive atoms, the overall rate of decay appears
> to be governed by the number of nuclei left undecayed.
> The time taken for half the radioactive atoms in a sample
> to decay remains constant and is called the half-life.
> Radioactive substances decay exponentially with time, and
> the value of the half-life for a substance can vary from
> a fraction of a second to billions of years."
>
> The best web site for this kind of info seems to be
> [ http://www.karaolides.com/alevel/alevel.html ],
> and I would especially call attention to this subpage;
> [ http://www.karaolides.com/alevel/node14.html ].
>
> Highly recomended.
>
> I have been doing a bit of thinking and I believe that, oddly
> enough, a sample of Radium that has a rate of decay that
> changes according to the half-life formula does not imply
> that the rate of "hits" to a Geiger counter or other detector
> of ionizing radiation will change. In other words, the
> intensity (particles per second) of the radiation at the detector
> does not get dimmer. Here is why:
>
> Consider a flat plate of radium that is emitting alpha
> particles. Only the alpha particles from the surface
> atoms will reach the detector, as radium (and just about
> any other solid) blocks alpha particles very well.
>
> As each Radium atom decays, it forms Radon. If the atom
> is at the surface the Radon, being a gas, escapes. Thus
> the surface of the radium sample stays 100% radium, and
> decay just makes it thinner, which has no effect on the
> intensity of the radiation. (the edges of the plate will
> also erode, which will reduce the effective area. this
> effect is easy to remove by using a mask that covers the
> edges of the sample. Ordinary paper stops alpha
> particles.)
The geometry of your model has misled you. A simple analysis will illustrate the
fact. Consider that
in half-life T, N/2 particles will decay. In the subsequent interval T+1, N/4
particles will decay.
Thus the intensity numerator (decays) has decreased, but the intensity denominator
(seconds) is
constant. The intensity goes down. Exponentially with time.
>
>
> I was all ready to calculate the second by second bias
> caused by the Radium half-life of 1620 years, but I
> don't think that it causes a bias until the plate gets so
> thin that it starts getting holes in it.
>
> It is trivial to shield out virtually all sources of outside
> ionizing radiation, and easy to make the radium source have
> much more output than even the unshielded background.
> The detector only detects ionizing radiation, so most cosmic
> rays, neutrinos, etc. will pass right through without causing
> a hit.
>
> My conclusion is that, using a careful design, the time between
> arrival of alpha particles at your detector is a true random
> number, the bias caused by imperfections in the timing circuit are
> less than 1 in 10 to the minus 15th power, the bias caused
> by external sources are less than 1 in 10 to the minus 16th power,
> and that both of the above biases may themselves be somewhat
> random, thus decreasing the bias by an unknown amount.
>
> For an example of a non-careful design, with measured data on entropy,
> compressability,, etc, see [ http://www.fourmilab.ch/hotbits/ ] and
> [ http://www.fourmilab.ch/hotbits/how.html ]. As an engineer who
> works with very precise measurements, I know that I could be much, much
> better at eliminating bias than the described setup.
>
> When I combine the low amount of bias from the technique above with
> the MOM (Massive Overkill Method) by XORing the results of various
> psuedorandom generators with the methods listed in the following web
> sites,
>
> http://www.random.org/essay.html
> http://webnz.com/robert/true_rng.html
> http://www.clark.net/pub/cme/P1363/ranno.html
> http://world.std.com/~dtd/random/forward.pdf
> http://lavarand.sgi.com/
>
> and with the fact that the only bias that survives the MOM is a
> bias that is shared by every single RNG that feeds the MOM, the
> resulting random numbers are almost certainly true random, even
> though you can never absolutely prove such an assertion.
------------------------------
** 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
******************************
