Cryptography-Digest Digest #842, Volume #13 Fri, 9 Mar 01 02:13:00 EST
Contents:
Elgamal (Vipul Ved Prakash)
Re: frequency "flattening" (Benjamin Goldberg)
Re: arbitrary-precision arithmetic (Benjamin Goldberg)
Q: Help needed -- reverse-engineering stream-encoder�sequence generator ("Vlad
ROMASCANU")
Re: library or function for file encryption (Benjamin Goldberg)
Re: frequency "flattening" ("John A. Malley")
Re: Monty Hall problem (was Re: philosophical question?) (Fred Galvin)
Re: One-time Pad really unbreakable? ("Trevor L. Jackson, III")
Re: Was there ever a CRM-114 Discriminator? (rob osattin)
Re: One-time Pad really unbreakable? ("Trevor L. Jackson, III")
Re: Elgamal ("John A. Malley")
Re: New unbreakable code from Rabin? ("Trevor L. Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Vipul Ved Prakash)
Subject: Elgamal
Date: 9 Mar 2001 05:27:43 GMT
Are there provably secure schemes for encrypting and signing with Elgamal
(analogous to Optimal Asymmetric Encryption and Probablistic Signature
Scheme for RSA) ?
best,
vipul.
--
Vipul Ved Prakash, http://www.vipul.net/
PGP Fingerprint d5f78d9fc694a45a00ae086062498922
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: frequency "flattening"
Date: Fri, 09 Mar 2001 05:48:45 GMT
Joe H. Acker wrote:
[snip]
> I'll describe informally what I'm looking for.
>
> I'm looking for an algorithm that finds for a given input that
> consists of signs of the alphabet A, an output such that the frequency
> of each sign in the output is equal to each other sign of the output.
> The frequency of the signs in the output should be equal for all
> signs. And because there are infinitely many possible outputs that
> suffice this condition, the algorithm should find the optimal (or at
> least a quite optimal) encoding, meant in the way, that the result
> should be as short as possible, but it's allowed that
> length(result)>length(input)
>
> Here's a sample: Let alphabet A={a,b,c}. Let C be the desired encoding
> function (of course, there must be an inverse decoding function as
> well), let F_text(x) be a function that returns the frequency of sign
> x (element of A) as it occurs in text, then the result result=C(text)
> should have the following property:
>
> F_result(a) = F_result(b) = F_result(c) = k
>
> I just mentioned Huffman-Coding because I suspect that such an
> algorithm can work similar to it, but its aim is not compression at
> all but to "flatten" frequencies to a uniform distribution. In the
> sample, even if the input would only contain a and b, the output
> should contain a,b,c with equal frequency.
>
> Will I have to work that out myself or is there such an algorithm?
Although the aim may not be compression, that is what the result is.
What you are describing is the effects arithmetic encoder, but not
necessarily one which works in binary. Consider arithmetic coding, with
input alphabet {a, b, c}, and which outputs a decimal-type fraction (ie
a decimal point followed by digits) but base three. Most arithmetic
coding tutorials first give an example with regular arithmetic, and an
output in base 10, and then show how it's done in base 2.
After compression into a [base 10] decimal number, each of the digits
0-9 will occur with approximatly equal frequency. After compression
into binary, each of the binary digits (0 and 1) occur with approximatly
equal frequency. There is no reason to suspect that it might be
different for base 3.
Your idea of huffman is on-track, but is slightly off. Huffman doesn't
quite have the granularity, if that's the term, to get the output
frequencies exactly even, or even close to it, without significant
modification.
Since arithmetic coding, in base 3, is probably going to be rather
awkward, what I would suggest is the following: Do two passes, one of
which encodes from your 3 symbol input alphabet, with it's varyious
probabilities for each symbol, into binary output. Then do arithmetic
DECODING, with a fixed relative frequency for each symbol of 1/3.
To perform the inverse transformation, first do arithmetic encoding,
with fixed frequencies for each symbol, all being 1/3 probable. This
results in a binary string, identical to the intermediate stage of the
original transformation. Then do arithmetic decoding, with the various
probabilities for each symbol just as they originally were.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: arbitrary-precision arithmetic
Date: Fri, 09 Mar 2001 06:00:02 GMT
Berton Allen Earnshaw wrote:
>
> Someone from comp.lang.c said that the following question might be
> better answered here in sci.crypt:
>
> What are the different arbitrary-precision arithmetic packages
> available?
He lied to you. The best place would be sci.math. However, we will
answer you anyway. Or I will, and others will point out what I miss.
Some packages I can think of offhand are: gnu mp, gmp, freelip, miracl.
There are many more, and your favorite search engine will show some of
them to you.
Also, some crypto libraries (which aren't special purpose arithmetic
libraries) have some amounts of big integer code in them. bcrypt and
crypto++ are two I can think of off the top of my head. The guy who
supports pegwit also has some math code available on his site.
> Which seem to be the best?
It depends. What do you want it for?
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: "Vlad ROMASCANU" <[EMAIL PROTECTED]>
Subject: Q: Help needed -- reverse-engineering stream-encoder�sequence generator
Date: Fri, 9 Mar 2001 01:10:13 -0500
Hello,
I am attempting to reverse-engineer a stream-encoder, which has an 8-bit
wide input/output bus. I suspect it is not something very complicated (the
encoder was not designed for encrypting data, but more as some sort of
identification mechanism of the form 'here is some input, is your output
what I expect it to be?').
I need some hints as to what to do in order to come up with a solution.
Here is some sample input/output (all values in hexadecimal), I'm showing it
because it exhibits a regularity (see bottom of message) that might prove
helpful:
Constant input of 0x00:
Output: 40 e5 4e a8 3e e3 4c a6 3c e1 4a a4 3a df 48 a2 38 dd 46 a0 ...
Constant input of 0x01:
Output: 41 e5 4d a8 3f e3 4b a6 3d e1 49 a4 3b df 47 a2 39 dd 45 a0 ...
Constant input of 0x02:
Output: 3e e5 50 a8 3c e3 4e a6 3a e1 4c a4 38 df 4a a2 36 dd 48 a0 ...
...
Constant input of 0xff:
Output: 13 6d 03 a8 11 6b 01 a6 0f 69 ff a4 0d 67 fd a2 0b 65 fb a0 ...
input = {n | n = 0...inf}:
Input: 00 01 02 03 04 05 06 07 08 09 0a 0b 0c 0d 0e 0f 10 12 13 14 ...
Output: 40 e4 4f a8 3a da 49 a6 44 f0 53 a4 3e e6 4d a2 28 dc 57 a0 ...
input = {lower_bound(1.5*n) | n = 0...inf}:
Input: 00 01 03 04 06 07 09 0a 0c 0d 0f 10 12 13 15 16 18 19 1b 1c ...
Output: 40 e4 4f a8 3a da 49 a6 44 f0 53 a4 3e e6 4d a2 28 dc 57 a0 ...
input = {n*2 | n = 0...inf}:
Input: 00 02 04 06 08 0a 0c 0e 10 12 14 16 18 1a 1c 1e 20 22 24 26 ...
Output: 40 e7 54 b0 4e fd 62 b6 3c f3 70 bc 4a 9 7e c2 78 ff 4c c8 ...
input = {n*4 | n = 0...inf}:
Output: 40 e1 42 98 1e cf 40 86 3c bd fe 74 1a ab fc 62 38 19 3a 50 ...
In all the constant-input cases, as well as in the 0 1 2 3 4...
input-sequence case, the output S[n+4] = S[n] - 2. Unfortunately, this does
not hold for more irregular input sequences (e.g. the last three cases).
I first though I was dealing with a LFSR (linear feedback shift register)
and tried to solve for the constant-0 input as a LFSR, but got no solution
for 16-bit and less LFSRs (I expect the period of the sequence, for constant
input, based on S[n+4] = S[n] - 2, to be around (256/2)*4 = 512 = 2^9).
So, what can I be dealing with? BTW, the encoder is built in hardware and
has a very secondary role, therefore I don't expect any expensive resources
(such as multipliers/dividers, or even adders/subtractors) to be allocated
to it, it's probably just a bunch of XORs, ANDs and ORs.
What tools can I use to analyze this beast?
Thanks in advance,
Vlad
[please (also) reply by e-mail if possible]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: library or function for file encryption
Date: Fri, 09 Mar 2001 06:06:39 GMT
������ wrote:
>
> Hi all.
> I want to encrypt text files and after saving to read these files with
> decryption.
> I use C language in linux.
> I am trying to make the program with this functionality, but I don't
> know which library or function to use.
I would suggest crypto++, available at:
http://www.eskimo.com/~weidai/cryptlib.html
> If you have any emample file or artical to refer, recommend me.
> Thank you.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: frequency "flattening"
Date: Thu, 08 Mar 2001 22:15:17 -0800
Mok-Kong Shen wrote:
[snip]
>
> The essence of my explanation is that you can use homophones,
> (i.e. by suitably mapping each input symbol to a number
> of output symbols) to obtain (in general) a more or less
> flat distribution of the output symbols (how these are
> coded is another issue, preferably with the Huffman
> scheme to optimize the number of bits) and that better
> results can be obtained with larger sets of output symbols
> (unless by chance one gets exactly equal frequencies). I
> suppose that my example has made it clear what you have to
> do with any real input symbol distributions. As said, you
> have to decide what kind of almost equal frequencies is
> acceptable to you and stop, otherwise you would finish with
> a huge set of output symbols and a correspondingly large
> ratio of ciphertext to plaintext. That homophones flatten
> the frequency distributions is well known. Being a rather
> simple concept, I don't think there is any special literatures
> about that.
There is published work on this idea.
First, check out:
"A Universal Algorithm for Homophonic Coding" by Christoph G. Gunther
and Asea Brown Boveri, Advances in Cryptology
EuroCrypt '88, pp. 405-414.
Abstract:
"This contribution describes a coding technique which transforms a
stream of message symbols with an arbitrary frequency distribution into
a uniquely decodable stream of symbols which all have the same
frequency."
And the next year there appears
"An information-theoretic treatment of homophonic substitution" by H.
N.Jendal, Y. J. B. Kuhn and J. L. Massey, Advances in Cryptology
EuroCrypt '89, pp. 382-394.
with cryptanalysis of the variable-length homophonic substitution (as
originally presented in Gunther's paper) from an information-theory
viewpoint.
The algorithm the OP seeks may be Gunther's universal algorithm for
homophonic coding.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Fred Galvin <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers,de.sci.informatik.misc,sci.math
Subject: Re: Monty Hall problem (was Re: philosophical question?)
Date: Fri, 9 Mar 2001 00:17:11 -0600
On Wed, 7 Mar 2001, Adam Stephanides wrote:
> But in the standard Monty Hall problem, you don't just know that
> there is a goat behind #3. You also know that if there is a car
> behind #1, then Monty could have opened door #2 but didn't. This
> knowledge changes the probabilities, and it has no equivalent in
> your assumption.
You're right, of course. I was just being dense. Thanks!
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Fri, 09 Mar 2001 06:24:35 GMT
Tim Tyler wrote:
> John Savard <[EMAIL PROTECTED]> wrote:
> : On Wed, 7 Mar 2001 11:00:09 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote, in
> : part:
>
> :>Only in mathematical never-never land. The OTP "specification" does not
> :>offer any prescription for the generation of suitable random numbers -
> :>and since no such recipe is likely to be forthcoming, the "provably
> :>secure" OTP will never make it off the paper and into the real world.
>
> : In that case, Las Vegas ought to find another industry with which to
> : support itself.
>
> Do casinos state that their games are "unbreakable, and provably so."
>
> This is the first I have heard of it. In fact I am aware of casinos who
> have had their systems beaten by individuals with sophisticated monitoring
> equipment, designed to detect non-randomness in the apparatus.
>
> You can read more about such exploits in a popular book on the subject:
> The Newtonian Casino - Thomas A. Bass -
> http://www.amazon.co.uk/exec/obidos/ASIN/0140145931/
>
> ``The true story of how a group of young physicists and computer
> scientists developed a computer to predict the results of roulette. They
> then smuggled the device into the casinos of Las Vegas, hidden in the
> soles of their shoes.''
I believe this is the same group described in the book "The Eudaemonic Pie". If
so then the key to their predictive ability was not statistical anomalies, but
the real-time prediction of the ball's trajectory. The math is fairly hairy in
that it has to represent the two effects that dominate the ball's behavior:
friction and tilt. If the table is almost perfectly level friction effects
dominate and the final resting place of the ball can be predicted to fall within
a fairly narrow segment of the wheel. (But modern wheels have finer decorations
than classic wheels of 25 years ago, and the finer features have a more subtle
effect which spreads the prediction widely).
If the table is far from level then the simple sinusoid dominates and the final
resting place of the ball on the wheel can be very easily predicted. Wheels that
are somewhat level are hard to model because there is no closed form solution to
the composite integral describing the position of the ball with respect to the
wheel.
> Surely you are not asserting that casinos are producing "perfect
> randomness"? All casino's have to do is to produce enough randomness to
> come out ahead of their clients, once the house margin is taken into
> account. I believe roulette is one of the best casino games, in terms of
> expected winnings per game - and there the house margin is 1/60 - hardly
> something which needs to produce randomness good enough for cryptographic
> purposes.
The skill of the operator has a dramatic effect on the "randomness" of the
wheel. Watch the film "Casablanca" for an entertaining treatment of this issue.
------------------------------
From: rob osattin <[EMAIL PROTECTED]>
Subject: Re: Was there ever a CRM-114 Discriminator?
Date: Fri, 09 Mar 2001 06:25:24 GMT
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
>
> While this page has a lot of accurate information, it also contains
> at least a few things I'd consider questionable. Just for an obvious
> example, while they accurately note that the B-52 is often call the
> "BUFF", they claim it stands for "big ugly fat fellow", while the
> expansion in wide use is "big ugly flying F'er."
Your expansion sounds a lot more plausible than theirs. Have you considered
contacting the FAS and telling them about the errors you spotted on their page? I
thnk they gather information from a lot of sources and publish it , sometimes
without checking it out thoroughly. As you have real life experience in a B-52,
they should appreciate your constructive criticism.
What about the crm-114? Did you ever see one on a B-52?
Rob Osattin
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Fri, 09 Mar 2001 06:32:38 GMT
Mxsmanic wrote:
> "Trevor L. Jackson, III" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> > As for the provability of quantum randomness,
> > do you believe in the original proof of that
> > the fine structure constant is 136? How do
> > you feel about the experimental evidence that
> > the value is 137 and the revised proof?
>
> I'm not familiar with either of them.
>
My personal opinions are insufficiently well informed to be interesting. My
skepticism in re our understanding of QM remains. TTBOMK the most advanced
opinion on the five competing QM theories is that none is adequate, but a
superior theory will have to partake of aspects of all five.
>
> To what extent do you believe that quantum mechanics accurately reflects
> reality?
Completely. But note that the assertion that quantum effects are provably
random are incidental to the theory rather than necessary to it.
> In particularly, do you believe that radioactive decay is
> truly random or not, and why?
IMHO there is insufficient information/understanding/theory to provide a
definitive answer to this question. Bell's inequality is quite suggestive,
but the games that have to be played with the data to make it conform are a
concern when we start talking about proof in the mathematical sense.
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Elgamal
Date: Thu, 08 Mar 2001 22:33:28 -0800
Vipul Ved Prakash wrote:
>
> Are there provably secure schemes for encrypting and signing with Elgamal
> (analogous to Optimal Asymmetric Encryption and Probablistic Signature
> Scheme for RSA) ?
D. Boneh, A. Joux and P.Q. Nguyen authored a paper, "Why Textbook
ElGamal and RSA ENcryption are Insecure" In Proceedings AsiaCrypt '00,
Lecture Notes in Computer Science, Vol. 1976, Springer-Verlag, pp.
30--44, 2000, explaining the need to preprocess short plaintext before
encryption with ElGamal and RSA. They state there is no current
standard like OAEP for ElGamal but they list four references to proposed
standards for preprocessing before using ElGamal.
You can find their paper at
http://crypto.stanford.edu/~dabo/abstracts/ElGamalattack.html
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: New unbreakable code from Rabin?
Date: Fri, 09 Mar 2001 06:46:58 GMT
Tim Tyler wrote:
> [EMAIL PROTECTED] wrote:
> : Tim Tyler <[EMAIL PROTECTED]> writes:
>
> :> Which is not as high as the authors seem to think and in no way justifies
> :> their apparently ridiculous security claims :-(
>
> : If you would actually read and understand their security claims you
> : would not be so likely to say this.
>
> At the head of this thread: ``"This is the first provably unbreakable code
> that is really efficient" Dr. Rabin said.''
>
> That seems to be the claim that a break is impossible.
>
> I seem to be justified in describing this claim as "apparently
> ridiculous". It doesn't matter /what/ the details of the system
> proposed are, there's no way such a description can be justified.
> Provably unbreakable codes are simply not known to exist.
It's not the "provably unbreakable code" that bother me, but the "really
efficient" bit. I have to admit complete, abject failure in connecting the
concept of a trustworthy public source of truly random bits at a bit rate
verging on the infeasible with the concept of efficiency. Did I miss an
inversion or something?
------------------------------
** 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
******************************
