Cryptography-Digest Digest #492, Volume #11 Wed, 5 Apr 00 08:13:01 EDT
Contents:
Re: Is this code crackable? ("1198")
Re: Looking for Algorithm ([EMAIL PROTECTED])
generator of Zp ("Goi Bok Min")
Q: Simulation of quantum computing (Mok-Kong Shen)
Re: Q: Entropy (Mok-Kong Shen)
Re: BBS again (Mok-Kong Shen)
Re: BBS again (Mark Wooding)
Re: Download Random Number Generator from Ciphile Software (Tom St Denis)
Re: How much to encrypt? ([EMAIL PROTECTED])
Re: Can anyone decrypt this? ("Geir Rastad")
Re: Q: Simulation of quantum computing ("J.Wallace")
RNG based on Blum Blum Shub (Tom St Denis)
Re: RNG based on Blum Blum Shub (Tom St Denis)
Re: generator of Zp (Tom St Denis)
Re: BBS again (Mark Wooding)
Re: Is this code crackable? (Richard Herring)
----------------------------------------------------------------------------
From: "1198" <[EMAIL PROTECTED]>
Subject: Re: Is this code crackable?
Date: Wed, 5 Apr 2000 13:54:01 +0800
If the key file can be safely sent to the other end without security problem
then there is no point of having any encrytion at all..
Jethro wrote in message <5owG4.81349$[EMAIL PROTECTED]>...
>I'm new to this subject, but I'd appreciate an experts opinion on this.
>
>I've written a program that generates a "key" file. The key file is a text
>file composed of 10,000 randomly-selected ASCII characters (character codes
>1 through 126, excluding the end of file character code 026). The
>characters were generated randomly using the CPU timer, mouse position and
>current ocean water temp and barometric pressure inputs for randomizer
>seeding.
>
>To encrypt a plain text file (of less than 10,000 characters, ASCII codes 1
>through 126), the ASCII value of each character of the text file is added
to
>the ASCII value of each character of the key file. This summed character
is
>then placed into the encrypted file. Therefore, the encrypted file
consists
>of the same number of characters as the unencrypted file and all the
>encrypted characters are ASCII character codes 127 through 256.
>
>To decrypt the encrypted file, the same key file is used, this time
>subtracting the key character from the encrypted character to obtain the
>ASCII value of the original text file.
>
>It works, but of course it requires one to physically give the key file to
>someone else. My question is, is it possible to crack this type of code
>without having the key file? I can't think of a way. Is this a well-known
>technique?
>
>
>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Looking for Algorithm
Date: Wed, 05 Apr 2000 08:37:54 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (wtshaw) wrote:
> In article <8carjm$mn9$[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> > Help!
> > I looking for an algorithm that does the following
> > - splits a message in 2 parts,
> > - hashes every line
> > - so that key and lock have always the same bit-length.
> > Maybe a stupid question, but i am new to cypto.
> > I have read about somewhere in the web , but I can't
> > remember the name of it - i need it for one of my projects.
> > Many thanks and a nice day
> >
> Forget line divisions with single carriage returns and line feeds as these
> are usually transparent to the user and not necessary for inclusion is a
> text stream. They were necessary to early teletype machines to make the
> receiver a slave to the transmitter. Everything goes well if the
> communications are sound, otherwise lots of ruined paper with garbage was
> need to be discarded.
>
> Computers can be more intelligent than that, but some presist in 150
> year-old thinking in this area.
> --
<smile> I understand very well what you are going to tell me - but the
hashing of every line is absolute necessary for the concept we are
thinking about. Maybe it is better not to talk about lines, but talk
about data-fields. Keeping these data-fields in correct order is also
necessary. Each data-field must be encrypted and hashed separate, cause
there will be user interaction, regarding which data-field being
transmitted between encrypting and decrypting.
This sounds to be strange - but sometime strange problems need strange
solutions.
Thanks for your help
Oliver
P.S.: don't let my answer to you sound as harsh as yours to me, remember
that I'm not a native speaker but I'm a (mostly) friendly guy. :-)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Goi Bok Min" <[EMAIL PROTECTED]>
Subject: generator of Zp
Date: Wed, 5 Apr 2000 16:50:32 +0800
Help... can some one help me on this?
recently, i came across the Chaum_van Heijst_Pfitzmann Hash Function which
basically based on discrete logarithm problem.
The algorithm is as following:
Let p =2*q+1 be a prime such that q is prime.
Let a and b be two primitive elements of Zp - Group p.
The hash function is defined as follows:
h(x1, x2) = (a^x1)*( b^x2 ) mod p belong to Zp\{0}.
where, the two messages block x1, x2 are belonged to Zq.
now, my problems are:
1) how can i calculate the "a" and "b" - the primitive elements given
primary "p"?
( here, i assume that primitive elements are equivalent to generator
which can be generate all non-zero of the element in Zp.)
2) supposedly, the order of generator is (p-1) - is it always true?
so that a^(p-1) mod p = 1.
but why a^q = -1 = p-1 (mod p) ?
3) i tried to obtain a generator by calculating:
g = h ^ k mod p, where h is an element of Zp and k is an integer.
UNFORTUNATELY, g obtained from this method , the order is
just q = (p-1)/2 but not (p-1). because g^q = 1 (mod p) not -1 as
above.
Thank you very much.
Goi
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: Simulation of quantum computing
Date: Wed, 05 Apr 2000 11:17:07 +0200
Some questions of ignorance:
Can one simulate a quantum computer with a common digital computer?
If yes, how to do that? Would that follow that one can obtain with
software alone the uncertainty inherent in quantum theory and hence
be able to get truly random bits that way?
If no, does that imply that a Turing machine can't simulate a
quantum computer and hence that the latter is more powerful?
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Entropy
Date: Wed, 05 Apr 2000 11:15:44 +0200
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> >
> > After reflecting a bit more about tossing a perfect coin, I
> > believe there is a paradox whose explanation I don't yet know.
> > If a perfect coin is tossed n times, it generates a bit
> > sequence of length n. How much entropy should I ascribe to
> > that sequence? Note that the result is one of the binary numbers
> > in the interval 0 to 2^n-1. Each of these numbers has an equal
> > chance of turning up in my experiment. Suppose by chance I get
> > the number 0, i.e. all n bits are 0. Should I still consider the
> > sequence to have some entropy and, in particular, the same
> > entropy as a sequence having an apparently fairly random pattern
> > of 0 and 1? Thanks.
>
> Once more: the information in a particular message text,
> measured in entropy, is not a property of the text alone,
> but of the text with its probability.
If I understand correctly, then your sentence should read:
The information in a particular message text, measured in
entropy, is a function of the probability of occurence of
that text and is independent of the property of the text
itself.
Do you agree? Anyway, you don't seem to have specifically answered
my question of whether the sequence of all 0 has the same or
different entropy as an apparently random sequence in the experiment.
According to the above, the answer should be yes. Now consider
applying compression to both, then they are likely to get compressed
to different lengths. Would that fact conform to their having
the same entropy? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: BBS again
Date: Wed, 05 Apr 2000 11:34:44 +0200
Tom St Denis wrote:
>
> Now that I know a little more about num theory. I want to ask how the
> BBS works. I will explain what I know.
[snip]
> What is the period of this generator?
> Do p and q have to be p- and q- strong?
There was a thread on that a bit back. You should consult Terry
Ritter's page at
http://www.io.com/~ritter/
for some of the problems.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: BBS again
Date: 5 Apr 2000 10:23:14 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> What is the period of this generator?
The period of a BBS generator with modulus n = pq is, apparently, the
lowest common multiple of the factors of p - 1 and q - 1[1]. If p and q
are chosen at random, p - 1 and q - 1 are likely to have distinct large
prime factors. Choosing p and q as safe primes (i.e., (p - 1)/2 and
(q - 1)/2 both prime) is a sufficient condition for maximum period. And
of course the product of two safe primes is automatically a Blum integer.
> Do p and q have to be p- and q- strong?
If p and q are strong primes, the resulting public key will be more
resistant to some (obsolete) factoring methods. Strong primes don't
make a difference to the general number-field sieve, but I believe that
it's conceivable that they might be stronger against future factoring
methods.
[Note: a strong prime p is such that (a) p - 1 has a large prime factor
(call it r), (b) p + 1 has a large prime factor and (c) r - 1 has a
large prime factor.]
For my BBS generator, I currently choose a pair of strong primes p and q
where (p - 1)/2 and (q - 1)/2 are relatively prime, although this is a
result of a poor reading of the above criterion. It should still result
in a period of at least sqrt(n), I believe, and with that being about
2^{512} I'm not sure I'm overly worried.
I don't know a good algorithm for finding primes which are both strong
and safe.
[1] My source is the help for the `srandom' function for `calc', an
arbitrary precision calculator written by David I. Bell et al.
-- [mdw]
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Download Random Number Generator from Ciphile Software
Date: Wed, 05 Apr 2000 10:48:09 GMT
Anthony Stephen Szopa wrote:
>
> Discuss the software. I do not want to have you exploit your
> erudition, and pontificate.
>
> If you have a point about the software make it and support it
> with fact.
>
> To do this you must have the software, have thoroughly read the
> Help Files, run the examples, and taken all the tutorials.
>
> If you will not do this I have no time to spend with such an
> unmotivated person.
Whoa, hold on right here. We are not working for you, if anyone even
looks at your "software" from an acdemic stand point it's because they
are being curtious. So stop pretending you are "teaching" a "class"
since you have yet to actually clearly document "exactly" what your
"processes" to. And no, I won't pick up a copy of the software. Just
write a paper [which I remember telling you to do about a year ago] on
your RNG and people can read that.
Tom
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: How much to encrypt?
Date: Wed, 05 Apr 2000 10:46:48 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Compare that with a
> theoretical attack that the cipher was designed to be resistant
> to, and that if it is not to be considered hopelessly weak by modern
> standards, would require more than 2^40 or so exactly-known
> plaintext/ciphertext
> pairs (or the equivalent keystream for a stream cipher).
This much we agree: If it is _proven_ that a key retrieval attack would
require more than 2^40 known plaintext/ciphertext pairs, then there is
no point in following my advice.
The problem, as far as I am concerned, is that in most cases you don't
really prove that when you test the strength of a cipher. A number like
2^40 might be derived from the most efficient attack that is both known
and feasible. If we are talking about absolute security, you should
only look at the number of pairs that is required by a brute force
attack that fully exploits plain text redudancy. No possible attack,
may it be known or yet unknown, will require less.
Also, if such an attack really would require 2^40 pairs, there might be
other problems with this. There might be attacks that will
unequivocally recover unknown plain text _without_ first unequivocally
recovering the key (because the function CSK(p,c) =
CorrespondingSetOfKeys(PlainText,CipherText) = {k0,k1,k2,...,kn} has
certain unwanted properties, e.g. that the intersection K * CKS(p,c) is
equal to K * CKS(p',c) for some CKS-intersection K, some english text p
and every english text p' that fits in context).
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Geir Rastad" <[EMAIL PROTECTED]>
Subject: Re: Can anyone decrypt this?
Date: Wed, 5 Apr 2000 13:01:21 +0200
OK: First create a table listing the frequency of all letters. You'll now
have a kind of idea
where some common used letters is placed (like O, R, T, E etc...)
Then use a pattern search as you've already gotten a clue: the word THAT
appears in it. Given the clue you can also assume, Hmmm, maybe it's all
uppercase/lowercase ???
you'll now have a few pattern matches. (But it don't look right! shouldn't a
space occur both before and after the word ??? Well maybe NOT!!!)
Choose the pattern you think is the right for this word (Maybe there's a
repeated pattern match, this is good!)
By now you should have T H A correctly....
mask out encrypted characters as they're only distracting by printing a .
instead.....
Play around with the most frequent letters (you still need E and O ;) ) and
you'll suddely find a new word appearing ....
HINT: The decrypted text speaks of privacy!
That's it for now ....
More hints
"John Stone" <[EMAIL PROTECTED]> wrote in message
news:8cberg$sks$[EMAIL PROTECTED]...
> I bet you think this is pitiful, but I still can't figure it out. Any
help
> would be greatly appreciated.
>
>
> "Jim Gillogly" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > [EMAIL PROTECTED] wrote:
> > >
> > >
>
$N!FZ@GW?CW$AYY!G@WC@AY?V!FYX$Y@H@G+X?R$FAG@$Y?G@*BA!FBY*Y?Y@ZY!Q@YX$YVG!W!?
> FZB@AG@Y$FZR+BY@G+Y!@HG+
> > >
> > > I know it is simply a substution encryption scheme, but I can't get
it?
> >
> > Do a frequency count. It's in English, so try to identify the most
common
> > letters: E, T, A, O, I, N and so on. If you get stuck, look for pattern
> > words... the word THAT appears in it. Often the beginning and ending of
> > a cryptogram are the easiest entries, but ignore the end this time: they
> > truncated the Dickens quote.
> > --
> > Jim Gillogly
> > Sterday, 8 Astron S.R. 2000, 19:12
> > 12.19.7.1.8, 6 Lamat 16 Cumku, First Lord of Night
>
>
------------------------------
From: "J.Wallace" <[EMAIL PROTECTED]>
Subject: Re: Q: Simulation of quantum computing
Date: Wed, 05 Apr 2000 12:01:50 +0100
Mok-Kong Shen wrote:
>
> Some questions of ignorance:
>
> Can one simulate a quantum computer with a common digital computer?
Feynman observed that classical systems cannot effectively model quantum
mechanical systems and proposed that the only way to effectively model a
quantum mechanical system would be by the use of another quantum
mechanical system.
A quantum computer simulator is an attempt to model a quantum mechanical
system on a classical system, the simulator must therefore keep track of
exponentially many computations in order to model the quantum mechanical
machine accurately. A simulation of a quantum computation is
exponential in both space and time. (If it were possible to contruct an
efficient quantum computer simulator then this would effectively be a
quantum computer).
However, there are a variety of quantum computer simulators available
that attempt to simulate aspects of a quantum computer. The simulators
differ significantly in the extent to which they simulate the quantum
mechanical aspects and some just experiment with simulating a particular
quantum algorithm (usually Shor's algorithm).
Links to quantum computer simulators can be found at:
http://www.dcs.ex.ac.uk/~jwallace/simtable.htm
Julia
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: RNG based on Blum Blum Shub
Date: Wed, 05 Apr 2000 11:23:39 GMT
What about changing it to
p = large prime, (p - 1)/2 is prime
X = seed
g = large primitive generator (modulo p), above (p - 1) / 2, with at
least log2(p)/2 bits set.
M[0] = g^X
To generate an output compute:
M[i] = M[i - 1] * g (mod p)
Y = M[i] mod 2^log2(p)
Y = output, so with a 256 bit prime, this will output 8 bits each
itteration. I know this is probably not strong, so where would you
start to attack it?
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RNG based on Blum Blum Shub
Date: Wed, 05 Apr 2000 11:24:52 GMT
I meant based on BBS type idea... sorry. It's not even close to bbs...
doh..
Tom St Denis wrote:
>
> What about changing it to
>
> p = large prime, (p - 1)/2 is prime
> X = seed
> g = large primitive generator (modulo p), above (p - 1) / 2, with at
> least log2(p)/2 bits set.
>
> M[0] = g^X
>
> To generate an output compute:
>
> M[i] = M[i - 1] * g (mod p)
> Y = M[i] mod 2^log2(p)
>
> Y = output, so with a 256 bit prime, this will output 8 bits each
> itteration. I know this is probably not strong, so where would you
> start to attack it?
>
> Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: generator of Zp
Date: Wed, 05 Apr 2000 11:30:20 GMT
Goi Bok Min wrote:
>
> Help... can some one help me on this?
>
> recently, i came across the Chaum_van Heijst_Pfitzmann Hash Function which
> basically based on discrete logarithm problem.
> The algorithm is as following:
> Let p =2*q+1 be a prime such that q is prime.
> Let a and b be two primitive elements of Zp - Group p.
>
> The hash function is defined as follows:
> h(x1, x2) = (a^x1)*( b^x2 ) mod p belong to Zp\{0}.
> where, the two messages block x1, x2 are belonged to Zq.
>
> now, my problems are:
> 1) how can i calculate the "a" and "b" - the primitive elements given
> primary "p"?
> ( here, i assume that primitive elements are equivalent to generator
> which can be generate all non-zero of the element in Zp.)
If your prime is p- strong, just randomly try 'g' values to get
g^p-1 = 1 (mod p)
g^(p-1)/2 != 1 (mod p)
Any 'g' that satisfies those too conditions is a generator mod p.
>
> 2) supposedly, the order of generator is (p-1) - is it always true?
> so that a^(p-1) mod p = 1.
> but why a^q = -1 = p-1 (mod p) ?
Yes the period for a multiplicative generator mod a prime 'p' is always
'p - 1'. I dunno about the a^q, except that if a is a generator a^q
should never be 1 (mod p).
Tom
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: BBS again
Date: 5 Apr 2000 11:48:05 GMT
Mark Wooding <[EMAIL PROTECTED]> wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> > What is the period of this generator?
>
> The period of a BBS generator with modulus n = pq is, apparently, the
> lowest common multiple of the factors of p - 1 and q - 1[1]. If p and q
> are chosen at random, p - 1 and q - 1 are likely to have distinct large
> prime factors. Choosing p and q as safe primes (i.e., (p - 1)/2 and
> (q - 1)/2 both prime) is a sufficient condition for maximum period. And
> of course the product of two safe primes is automatically a Blum integer.
Oh, goodness. This is wrong too :-(. A quick squint at
http://www.contestcen.com/crypt001.htm reveals a more gloomy picture.
If p = 2 p' + 1, and p' = 2 p'' + 1 with p, p' and p'' prime, *and*
similarly for q, q' and q'', then the BBS generator with modulus
n = p q has a maximum period of 2 p'' q''. Generating large primes of
this nature will be rather time-consuming.
See the web page for more information, together with some
experimentation with small Blum moduli.
I'll now stand aside and let people who really know about this sort of
thing start to discuss it.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Is this code crackable?
Date: 5 Apr 2000 11:26:17 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, 1198 ([EMAIL PROTECTED]) wrote:
> If the key file can be safely sent to the other end without security problem
> then there is no point of having any encrytion at all..
Not so. You're assuming that a channel that is "safe" now will
always be safe.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
** 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
******************************
