Cryptography-Digest Digest #892, Volume #8 Tue, 12 Jan 99 14:13:03 EST
Contents:
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: Practical True Random Number Generator (Medical Electronics Lab)
Re: RSA-Modulus decomposition (Jim Felling)
Re: On the Generation of Pseudo-OTP ("Tony T. Warnock")
Re: Comments & note for Bryan (Re: coNP=NP Made Easier?) (ilias kastanas 08-14-90)
Re: Practical True Random Number Generator (Medical Electronics Lab)
Gartner Group Recruiting InfoSec Analyst (VictorW318)
Re: Random numbers in C: Some suggestions. (George Marsaglia)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 16:42:29 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 12 Jan 1999 08:26:02 -0500, "Trevor Jackson, III"
<[EMAIL PROTECTED]> wrote:
>Please review the following sections of RFC1750:
>4.4 Selecting keys from large databases; why this is a bad idea.
Yes I saw that. I wonder if it should be updated in light of the
Internet.
>N.B., a transcendental
>number is a compressible form of lage database.
Yes. But if the offset is 128 bits in length, who cares? And if
several such "random" transcendental constants are strongly mixed, an
even smaller offset can be used.
>5.2.3 Removal of correlation via FFT
>6.1.2 Strong mixing functions.
>These sections address the major issues you've raised recently.
Yes, but are they certifiably secure methods of removing correlation
in bitstreams, even to a practical level?
Just because NIST promotes them is no assurance of their cryptographic
strength.
Bob Knauer
"Anyone that can get elected, is not qualified to serve."
--Lance Bledsoe
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 12:18:22 -0600
KloroX wrote:
> Does anyone have pointers to on-line schematics/explanations of the
> electronics in a ionization-type smoke detector? As I understand it,
> alpha radiation ionizes the oxygen and nitrogen in the air, which then
> flows to one of the charged plates in the detector. Smoke absorbs some
> of the ions, and the reduced current flow is detected. For this to
> work, a rather steady flow of ions must be necessary, so it might be
> difficult to resolve the flow into individual "hits". Perhaps the
> detector cannot be used without sibstantial modifications.
I haven't put anything on line yet, but I've been working on this
off and on for the past few years. I've taken the source out of
a smoke detector and disassembled it. I've also added plenty of
well shielded electronics and have worked with a professor of
statistics to ensure the output is "random" in the mathematical
sense. It's gotten close to perfect, but it ain't good enough
for me yet until it *is* perfect.
The ion source consists of 3 main parts: the radioactive source,
a sense grid and an anode. I draw it like a triode (that's a tube
for you young'uns) with the source grounded. Physically, the
source I have has a 2 cm disk for the source embedded in plastic
which holds up a disk of metal (aluminum or steel I think) which
has a 1 cm diameter hole in it. About 1 cm above and completely
surrounding the plastic is a steel shell with holes in the top and
sides. The shell is the anode. All dimensions within a factor
of 2.
The basic operation of the smoke detector is to measure the dc
level of the grid. The ionizaion source (5 MeV alphas from
Americium 241, half life 470 years, 1 microcurrie) keeps the air
charged with positive and negative ions. I ignore the free electrons
in my models because they are recaptured in less than a microsecond.
When smoke enters the detector, it sucks up ions and the grid
voltage drops. The detector is sensative, it only takes a few
parts per million to change the dc level.
I can see individual ionizations. They are basicly sound pressure
spikes. The overall signal has the typical 1/f amplitude distribution
you expect from a real noise source. My electronics filters out
most stuff below 200 Hz and everything above 5kHz. An FFT of the
raw signal shows a spike around 3.6kHz which is the decay rate
convolved with the geometry of the detector.
I'm still trying to get a good way to maximize the data rate. So
far we've gotten several algorithms which give either uniform
distribution, but not random, or good randomness that isn't
uniform. Until it's perfected, there's no point going into
too many details.
Suffice it to say, it has not been easy to keep a professor
of statistics happy with the output! But I'm getting there, and
when it works, I'll write it up.
Patience, persistence, truth,
Dr. mike
------------------------------
Date: Tue, 12 Jan 1999 11:16:36 -0600
From: Jim Felling <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To:
alt.privacy,alt.security,alt.security.pgp,comp.security.pgp.discuss,talk.politics.crypto
Subject: Re: RSA-Modulus decomposition
I hate to say this, but -- aernst331 does not make silly, untrue claims.
He makes very, very silly/useless true claims. Yes his methods will work -- mind
you many of them are actually less efficient than random guessing, due to the
cost of computing squares vs trial divisions or the cost of doing tons of
multiplies with his 'cycle method ' of some weeks ago. Who knows, if he keeps
this up long enough he may come up with something, but I kind of doubt it.
David Hamilton wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
>
> [EMAIL PROTECTED] wrote:
>
> >Hello all,
>
> >It is very easy to find decomposition of a
> >modulus to it’s primes.
> >Let n=pq be a modulus. Let m be a least
> >message for which m^2 mod n = m.
> >Then m-1 is p or q.
>
> (snip some)
>
> This is how things are. Alex ([EMAIL PROTECTED]) makes silly, untrue
> claims. People issue challenges that give him/her a chance to prove those
> claims. Alex refuses to accept all challenges. Why? Because Alex makes silly,
> untrue claims.
>
> David Hamilton. Only I give the right to read what I write and PGP allows me
> to make that choice. Use PGP now.
> I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
> 2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
> 4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
> Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
> -----BEGIN PGP SIGNATURE-----
> Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
> Comment: Signed with RSA 2048 bit key
>
> iQEVAwUBNpZQOso1RmX6QSF5AQHVAAgApK3JRo94kTQan/KBa84FipmGg8f0MT4f
> Qi01pIOTN2d2dcya8xur9EfmzKRUh541XlzpgFXuz/zVZMfd9qBKbvRtIXPsH0Bh
> X7unFNGm8Tzebn2/Sni5mzqshQCDiaiAuHRAA7eJtT9QaLgcQjsKF0q4uHcF+Ccx
> wKtwH9QDc+AEFMaSrwvwUAzo1PVRon2xJuW0hzb4OAFxK8FFAnzr4vi5RAsJ4b6g
> 9OYeHK9KEobzSnb07VzXroNYIHSB8vg6tD4Eb1zWtPcx71Z0X1c+R3Yx9pTxDiPT
> AqpChj3c5XPLlMGumWNz0xP9SZL0/Z7ZfFPVgfBm7ki1O1FJxV7UZg==
> =yEa7
> -----END PGP SIGNATURE-----
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 12 Jan 1999 08:18:19 -0700
Reply-To: [EMAIL PROTECTED]
Trevor Jackson, III wrote:
> Do yo believe it proper to describe the cipher system attacked in the
> Venona project as an OTP or not? Both the Russians who operated the
> system and the attackers considered it to be an OTP. Probably becauseit
> was supposed to be based on single-use keys. The quality of the keys is
> irrelevant to the classical term OTP.
>
> Your very narrow definition does not match the classical definition of an
> OTP.
Actually the Russians' protocol lapses turned their OTP into a two-timing
pad.
Tony
------------------------------
From: [EMAIL PROTECTED] (ilias kastanas 08-14-90)
Crossposted-To: sci.math,comp.theory
Subject: Re: Comments & note for Bryan (Re: coNP=NP Made Easier?)
Date: 12 Jan 1999 17:11:55 GMT
In article <[EMAIL PROTECTED]>, rosi <[EMAIL PROTECTED]> wrote:
@Nothing is serious stuff here. Just a few comments and repetitions.
Plus lots of misstatements about me, copious snide remarks,
and vacuous rhetoric.
@ This Planar reminds me of another occasion, which I took care
@not to make it look like bickering and get everybody distracted
@from the real issue. Now Ilias is in agreement (though an awkward
@type) with me. I can spend a few sentences.
I'm afraid I'm not.
@ It would be a real nice patch, I think, to agree with Planar and
@do 'P by DTM'. (That's from a book? It must make perfect sense! Be
@it in some volume, but is it God's creation or creation by God's
@creation?)
Look, P is _defined_ as "solvable by pol. time DTM" (what this is is
spelled out in detail); yes, in all textbooks and all papers. Everyone who
uses the symbol "P" means the above. You don't get to "agree or disagree"...
any more than with using the symbol "3" for the number of strokes in |||.
@ If there is any mechanism, including a piece of magic
@ rock, that solves SS positively in P, then coNP=NP.
@
@ I also made it explicit and clear about what happens to
@coNP?=NP if no such mechanism exists.
No, you gave no argument for this case.
@ In the construction of the mechanism for the argument, I by
@chance used the notion of 27. Some may think that I think 27 is
@better than 26. I NEVER said that. But it is obviously not that
Again: the term "pol. time NDTM solves X" has been _defined_ as
"if input is in X, _some_ possible computation prints YES; if not, none does".
That is, as in 26. (And "NP" as the set of all such X).
Like it or hate it; the words "pol. time NDTM solves X" are a
symbol standing for the above. Maybe, in your opinion, "that's not _really_
'solving'!...", "it's a bad choice of terminology", or whatever. It makes
no difference; the definition is what it is.
You brought up 27, the notion "prints YES _if and only if_ input is
in Z" (i.e. _all_ possible computations for that input do so). Fine; let's
call it: 'pol time NDTM "rosi-solves" Z'. The set of all such Z we might
call "NP*".
It turns out that 'a pol. time NDTM "rosi-solves" Z' iff 'some
pol. time DTM solves Z'. That is, NP* = P.
@obvious that it can be a piece of ... as well. (Did I mean it is
@a piece of ...? NO! I say if it ever is, it is not as obvious
@as 26.) AND once again, the main point is: I do not care what
@mechanism. (I do not care how one defines P, either. I say if
@NDTM is realizable, coNP=NP.) By the way you can fill in
You argue, "if a pol. time NDTM rosi-solves SS, then NP=coNP".
Well, 'a pol. time NDTM rosi-solves SS' iff P=NP; and it's hardly news
that 'if P=NP, then NP=coNP'.
What if P != NP (i.e. if SS can't be rosi-solved)? You have
no argument for this (the interesting) case.
@ Ilias holds:
@ 1. my argument does not work because NDTM (K) behaves
@ as described in 26.
No.
I described K, a pol. time NDTM that solves SS; (yes, "solves"
as in 26). That shows SS is in NP. [A separate argument shows that
SS is also NP-complete].
Your argument does not prove that "NP=coNP"; it only proves
"P=NP -> NP=coNP"... a trivial, well-known result.
@ 2. NDTM (K) exists (though no realization of it is needed)
Eh?... I spelled out K explicitly; how it erases, adds, compares...
Planar gave you an equivalent machine, explicitly and formally too.
@ NOTE: Whether he meant that he could provide the proof
@ or such a proof existed for the existence of NDTM's but
@ a realization might never be achievable, I am not sure.
@ He as usual did not commit. He said he would not want
Please quote me verbatim rather then attempting to paraphrase and
getting everything wrong.
@ to disagree with Church, his Advisor^n for some natural
@ number for which Advisor^n is defined. He also expressed
@ that he did not know the difference between Turing's
@ Thesis and Church's Thesis. I leave it at that.
I don't disagree with Church -- not because he is Church, but
because I read his proofs and found them correct. What is it that you call
"Turing's Thesis"? And what is your hang-up with "advisor^n"?
@ 3. (I quote):
@ The mechanism's existence (i.e. P=NP)
@ trivially implies NP=coNP.
@ NOTE: Hope this is not an editorial thing. :)
Hope you don't imagine I'm saying "a mechanism does exist"...?!
@ I only have slight different opinion with Ilias concerning the
@difficulty of the derivation. We both seem to hold that coNP=NP
@(under the pretext that NDTM is real) is a trivia. We seem to
@differ in the ultimate treatment. I think I still have to show
@why it is a trivia to let the world see why it is trivial. (And
@I have to arrogantly assume that the world did not see it as a
@trivia although it does)
No kidding? P=coP (proof: switch YES and NO); so if P=NP,
then coNP = coP = P = NP. Trivial enough?!
@as well. But how do you say that X is more complex than Y? Because
@a TM (algorithm) that can solve Y in O(n) can not solve X in O(n)?
How do you come up with stuff like this??
Some TM solves Y in O(n), but no TM solves X in O(n)... huh?
@Because DTM can not solve SS within polynomial bound (but a
@different algorithm NDTM can), SS is more complex than sorting an
@unordered list? Is that your complexity theory that O(n^k) is more
@complex than O(n^k)?
No, it's just your persisting confusion, that NTIME(n^k), nonde-
terministic, and TIME(n^k), deterministic, somehow amount to... the same
thing, a thing you call "O(n^k)" (!!?).
SS is "solved by a NDTM in O(n^3)" -- in the sense I described
above; not "rosi-solved". I.e. it is in NTIME(n^3). But it might not be in
TIME(n^k) for any k (that's what P != NP means); if so, it _is_ more complex
than sorting, a member of TIME(n log(n)) and hence of TIME(n^2). Then again,
maybe P=NP and SS is in TIME(n^4)... or in TIME(n log(log(n)))... or
somewhere (in which case I'll eat my hat).
@ One word about Ilias's agreeing with me: I say A. Ilias first
@says A is erroneous. After much ado, Ilias says in his own words
@that A is correct. Ilias immediately after, it seems to me, starts
@refuting anything that A is composed of. Well, not everything.
I've been saying the same thing throughout. These are your
stages of misunderstanding it.
@Ilias painstakingly showed why K could not make H work in an
@explicit, detailed and representative way, even though I have
@said all the way along and said explicitly right after I gave H.
Uh?... You only said H showed the definition of "NDTM solves.."
(26) was non-acceptable somehow. Which was more of the same confusion; H
is completely irrelevant to the issue. As I told you then, K doesn't have to
"make H work", or whatever else you mistakenly associate with "solves".
K satisfies the stated definition of "solves"; that's that. You don't
like calling that sort of thing "solving", it seems. But so what? It
_is_ the definition of NP.
@ A word for Bryan Olson. Dear Bryan, I keep my promise to
@discuss coNP=NP with you. I regret though. It is nice that you
@did not commit to 26 till Ilias showed (in principle I think) NDTM
@as described in 26 does not work. Good timing! But I thought you
By "does not work" you mean "does not rosi-solve". Right, K
doesn't rosi-solve SS. So? It doesn't have to. It only "solves",
i.e. shows SS is in NP. A TM _rosi-solving_ SS would mean P=NP.
@ I would like to remind you of one of his familiar themes:
@ It is theory (high stuff). It works. I do not have to
@ show you how. It just works. But if you use it in any
@ way, it does not work. It is because you are wrong.
Rationalize away. You interpret words not by their definitions but
by what you think they mean. Astounding obstinacy... You were told dozens of
times the definition of "ND solving", e.g., to no avail. No wonder then
things don't make sense... and you delude yourself "I didn't show you how".
@ Lastly for you Bryan. If you want to discuss the issue, you need
@to commit to getting this to the end responsibly and give me _YOUR_
@NDTM (you can copy from anywhere you care to) and show us exactly
@how _YOUR_ NDTM solves SS in polynomial time.
See what I mean? You're asking for yet another NDTM for SS; you think
K, or Planar's, or others', don't "work". They _do_; they satisfy the defi-
nition of "NDTM solves in pol time"! You, however, are interpreting
"NDTM solves in pol time" your own imagined way.
Well, since you reject K -- why is SS in NP, according to you?
What is the definition of NP, and how does SS satisfy it?
You've posted distortions of my views, forcing me to reply and
set them right. It's unpleasant, and a waste of my time. Please don't
do it again.
Ilias
------------------------------
From: Medical Electronics Lab <[EMAIL PROTECTED]>
Subject: Re: Practical True Random Number Generator
Date: Tue, 12 Jan 1999 12:19:53 -0600
Mok-Kong Shen wrote:
> I just want to recall that the Diehard package as supplied by its
> designer is buggy. Sometime ago some person did a new implementation
> in C without the known bugs and announced it in this group. But his
> URL appears to be no longer accessible.
I saw your previous postings. We're using only binary inputs,
as well as lots of other routines/algorithms. Partly due to your
warnings, thanks!
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (VictorW318)
Subject: Gartner Group Recruiting InfoSec Analyst
Date: 12 Jan 1999 16:26:15 GMT
Gartner Group is recruiting analysts for our Information Security Strategies
service. Preferred are individuals with user organization experience, good
product knowledge, and the ability to critically analyze and present in writing
and in presentations, both formal and informal. Topic areas needed: including,
but not limited to Professional Services (evaluating the providers), Intrusion
Detection, Financial Institution requirements, network security, business
recovery. About one-fourth travel required. Prefer candidates near one of our
research centers in Stamford, Ct, San Jose California, or outside Boston but we
are flexible on location.
Resumes submitted through the undersigned will be directly forwarded to the
appropriate hiring managers as well as Human Resources. Candidates are welcome
to contact me for a preliminary discussion of position requirements. Personal
meetings for candidates already in the Northern California area and coming to
the RSA Show are possible.
Please forward vita, and if possible writing samples in confidence asap.
Victor S. Wheatman
Vice President - Information Security Strategies
Gartner Group
251 River Oaks Parkway
San Jose CA 95134-1913
[EMAIL PROTECTED]
-
FAX: 408-954-1780
(no calls please!)
------------------------------
From: George Marsaglia <[EMAIL PROTECTED]>
Crossposted-To: sci.stat.math,sci.math,sci.math.num-analysis,sci.physics
Subject: Re: Random numbers in C: Some suggestions.
Date: Tue, 12 Jan 1999 13:56:41 -0500
Charles Bond wrote:
> Thanks for the post. I want to comment on the SWB routine. I've been
> using
> a similar routine in high speed simulations for years. ...
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
Many years? It hasn't been very many years
since I invented the subtract-with-borrow method,
and developed theory for establishing the periods.
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
> . I believe Knuth briefly discussed the method with guarded
> approval -- constrained by the concern that there was no real theory
> behind it. Do you know if any theoretical work has been done since
> Knuth's book to justify SWB?
> &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
> This business of providing 'theoretical support' for
> RNG's tends to be overdone---perhaps
> because of the influence of Knuth. His marvelous
> expository and poweful mathematical skills have
> justifiably made him the leading authority.
> Many people do not understand that such theory
> is based on the simple fact that congruential
> random numbers "fall mainly in the planes",
> that is, points whose coordinates are succesive
> elements from the sequence lie on a lattice
> with a huge unit-cell volume, (m^(n-1) in n-dimensions),
> compared to the unit-cell volume of 1 for truly random
> integers. So the "lattice test", as I called it,
> applies to congruential generators, although the ideas have
> been extended to the near-lattice-like patterns of
> certain other kinds of generators. But there seem
> to be no such lattice-like patterns for many other
> kinds of generators, and even if there were, it
> is an easy matter to destroy such patterns by
> combining with generators having disparate mathematical
> structures.
>
> The quote from my Keynote Address at the 1984
> Computer Science and Statistics: Symposium on the
> Interface, still applies:
>
> "A random number generator is like sex:
> When it's good, its wonderful;
> And when it's bad, it's still pretty good."
>
> Add to that, in line with my recommendations
> on combination generators;
>
> "And if it's bad, try a twosome or threesome."
>
> George Marsaglia
------------------------------
** 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
******************************
