Cryptography-Digest Digest #969, Volume #9 Mon, 2 Aug 99 10:13:06 EDT
Contents:
A most useful cipher (wtshaw)
Re: With all the talk about random... ("Robert C. Paulsen, Jr.")
Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a Byte?)
(Martin Ambuhl)
Re: Is breaking RSA NP-Complete ? (Safuat Hamdy)
Cryptanalysis of R250 (The Evil Anti-Rick)
Odp: Hash functions chapter from Handbook of Applied Cryptography ("Bartek Z.")
Re: Is breaking RSA NP-Complete ? (David A Molnar)
Re: cryptography tutorials (David A Molnar)
Re: Intel 810 chipset security (Vernon Schryver)
RSA Cryptography Today FAQ (1/1) ([EMAIL PROTECTED])
Re: question: SHA --> stream cipher (Krunoslav Leljak)
CFB mode with same initialization vector (Daniel Vogelheim)
Re: Another random question (fungus)
Re: Is breaking RSA NP-Complete ? (Helger Lipmaa)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: A most useful cipher
Date: Mon, 02 Aug 1999 00:40:36 -0600
When we type on a keyboard, we do a most un-ASCII type of thing: While
presented with 47 standard lower case character keys, we shift into
alternate upper case ones to give us the basic 94 in the lower ASCII set.
We also routinely use the space key and double return for a blank line
between paragraphs.
Well, 47 characters, plus 1 for shift and 1 for space gives us a set of 49
characters, quite handy for converting to certain other bases.
Mafra, there is such a place, converts base 49 to base 26 by way of base
seven information units, hepits. Each character in base 49 can be
represented by 2 hepits, 5 characters as 10 hepits, 10 characters as 20
hepits. These 10 or 20 hepits can be transposed according to a key. And,
they can be converted to 6 or 12 common alphabetic letters, base 26.
The base set and order for 49 characters is the 47 character keys on the
keyboard, top left to right, top to bottom, to bottom right, plus shift
and space. That's right, letters in two cases, digits, all the embossed
symbotls. The application frontend cuts multiple spaces to one in
preformatting, but two spaces are made to represent a double return blank
line.
I could have made a substitution key of 49, but left it alone, choosing
fairly simple keys for this application. Default keys (for Mafra 20) are:
Subs(Ma): abcdefghijklm nopqrstuvwxyz
Trans(Ma): abcde fghij klmno pqrst
In summary, in Mafra, plaintext groups are 5 or 10 characters, ciphertext
groups, 6 or 12. The application will NOT see tabs, multiple spaces, or
single returns, but handles everything else on the keyboard, outputting
only alphabetic letters, either case OK. If you need to make a list,
double space it.
Even with default keys, any simple or complex passage can be simply
converted to alphabetic letters. For instance, these words in this
paragraph can be converted letters and forced into classic groups to look
like this:
yahsx qyncw piyqw fsajz xoeuh uwyow nqkrs xkpog bayoz kqrlc tgbat ujfmk
nzjig vubtd obicy wvlln mrtjl coswq iumdn dlecu grqae wlako pxuti uyeto
xivtx fiqcy khixn cwcwv mmybn wmwjh iktyv ivvcm ygofg flznn ejaoq gcqea
yujhc ilcos wqium dnuhu oltyo fguvz yrebf rhxrw vkiwe yexnm kwvhy rkira
lltwo yysnb owysm xswyn zmduy fqwwi nyafe vtsjf
Remember, spaces are characters, the most of common category, and all
shifts are characters. There is really only a 20% expansion involved, but
you cram most of the scope of the keyboard represented in plaintext to
something easily confused as cipertext by any of many other systems. I
did not intend to produce here a very strong application with lots of
keys, but more of something in a simple format conversion utility.
A obvious use would be to chain this application's ciphertext with
something of a classical nature that only works on letters, such as has
been recently discussed in another thread.
The sets involved in these various applications are selected for my
convenience, but there is no reason that the same principles could be used
to cater to some other language set.
--
It is fine and dandy to choose to serve the government. It is fine
and dandy to obtain government services. It is still another thing
to find some in the crypto field have been serviced by government,
with contemplations of how they might do it better in the future.
------------------------------
From: "Robert C. Paulsen, Jr." <[EMAIL PROTECTED]>
Subject: Re: With all the talk about random...
Date: Sun, 01 Aug 1999 12:52:15 -0500
Herman Rubin wrote:
>
>
> There are stochastic effects, due to imperfections and thermal
> noise, which increase the lack of determinacy. If we roll the
> die far enough, quantum indeterminacy in the actions of other
> objects will introduce randomness.
>
That seems like a natural explanation to me too, but when I made
such a suggestion in another thread a few weeks back several people
replied saying essentially that ...
a) There was no quantum indeterminacy involved in dice rolling, and
b) quantum indeterminacy was not required to get true randomness
from rolling dice.
As far as I know, the only behavior in the universe known to
involve true randomness is is from quantum effects.
Other stochastic effects, chaos, complexity, etc. are just ways of
describing or dealing with situations where we lack enough
information to make predictions based on the underlying determinacy,
even though this information is obtainable in principle.
It is not unheard of for quantum randomness to make itself known on
a macroscopic scale -- a Geiger counter is the obvious example.
Perhaps rolling dice is another example. I really don't know if the
results of dice rolling actually is effected by quantum
indeterminacy but it would be interesting to see a "proof" one
way or the other.
--
____________________________________________________________________
Robert Paulsen http://paulsen.home.texas.net
------------------------------
From: Martin Ambuhl <[EMAIL PROTECTED]>
Crossposted-To: alt.comp.lang.learn.c-c++,comp.lang.c++,microsoft.public.vc.language
Subject: Re: How to write REALLY PORTABLE code dealing with bits (Was: How Big is a
Byte?)
Date: Mon, 02 Aug 1999 02:08:59 -0400
"Lame K. Irony" wrote:
> By the way, I'd like to point out the obvious fact that if the word "byte"
> did NOT mean an eight bit binary number, then it would necessary for us to
> create a word that DOES have that meaning, since there is certainly a need
> for such a word. In my opinion, the fact that no other such word exists is
> ample evidence that "byte" fits the bill.
Next time you get involved in a thread, stay awake. There have been
numerous uses of "octet" in this thread. Somehow people have been using
a word that that does not exist.
If you think "byte" works with the meaning "8-bits", explain what the
PDP-10 insruction LoadBytePointer is supposed to do when someone tries
to use one of the other 35 allowed sizes (any size 1-36) works.
--
Martin Ambuhl [EMAIL PROTECTED]
__________________________________________________________
Fight spam now!
Get your free anti-spam service: http://www.brightmail.com
------------------------------
From: Safuat Hamdy <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: 02 Aug 1999 08:38:38 +0200
Scott Fluhrer <[EMAIL PROTECTED]> writes:
> >All the public knows (to my knowledge) is that COMPOSITES is in NP n co-NP
> >(well, ok, we know that PRIMES is in ZPP, and since PRIMES = co-COMPOSITES
> >and ZPP is closed under complement, COMPOSITES is in ZPP).
> Q: What's ZPP? Is it something similar to RP (randomized polynomial time)?
ZPP is the class of sets which can be recognised by TMs probabilistically in
polynomial time, where the error is zero, but the TM may output "don't know"
instead of "yes" or "no", in other words, if the TM can compute an answer it
outputs the answer and this answer is always true (Las Vegas-type). Of
course, the TM must not say "don't know" too often.
> [...] To make it precise, all you need to
> do is replace the general "factoring" problem with the "has a factor less than"
> problem [...]
true, but unfortunately traditional efficient compositeness tests such as
Rabin-Miller doesn't tell you this.
--
S. Hamdy | All primes are odd except 2,
[EMAIL PROTECTED] | which is the oddest of all.
|
unsolicited commercial e-mail | D.E. Knuth
is strictly not welcome |
------------------------------
From: The Evil Anti-Rick <[EMAIL PROTECTED]>
Subject: Cryptanalysis of R250
Date: Sun, 01 Aug 1999 13:02:03 -0500
Does anyone have any cryptanalysis information on the R250 PRNG
algorithm and/or cryptanalysis information of byte-wise XOR stream
ciphers?
An an exercise, I wrote a simple XOR stream-cipher using R250 as the
RNG. That was the easy part. I looked through all my old textbooks for the
equations needed to break such a cipher and came up empty-handed. I recall
that it seemed pretty straight-forward, and it was presented as an acedemic
exercise for first-year crypto students.
Any pointers, links, answers and/or useful incantation would be
appreciated. Pointless criticisms or other wastes of bandwidth will be
re-directed to /dev/null.
--R. Pelletier,
Sys Admin, House Galiagante
and Amateur Cryptographer
------------------------------
From: "Bartek Z." <[EMAIL PROTECTED]>
Subject: Odp: Hash functions chapter from Handbook of Applied Cryptography
Date: Mon, 02 Aug 1999 08:22:43 GMT
For me it's cool! I live in central Europe (Poland) and it's impossible to
buy the book here (no translation). To import the booke you have to have a
credit card (which is hard to get if you don't have permanent job e.g.
you're student) and $90.00 it's quite a lotta money here as for a book (even
such good).
Anyway, I'm going to be on a vacation soon and I'll go to Springer bookstore
in Berlin and I'll buy it.
Regards,
Bartek
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: 2 Aug 1999 02:23:02 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
>>All the public knows (to my knowledge) is that COMPOSITES is in NP n co-NP
>>(well, ok, we know that PRIMES is in ZPP, and since PRIMES = co-COMPOSITES
>>and ZPP is closed under complement, COMPOSITES is in ZPP).
> Q: What's ZPP? Is it something similar to RP (randomized polynomial time)?
ZPP is that subset of RP which is closed under complement. Another way of
putting it is that it's the class of Las Vegas algorithms -- algorithms
for which the answer is guaranteed to be correct, but which have only an
'expected' running time.
You can read it as "zero probability of error, expected poly time."
As a probably useless but fun aside, note that PRIMES is in P (i.e. a
deterministic algorithm exists) if the Generalized Riemann Hypothesis
holds. Right now I'm working through the explanation given in Bach &
Shallit _Algorithmic Number Theory : Volume 1, Efficient Algorithms_; it's
proved to be a clear reference relative to the books I found on analytic
number theory (if a bit sketchy in parts...).
-David Molnar
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: cryptography tutorials
Date: 2 Aug 1999 02:32:15 GMT
Bobby Heffernan <[EMAIL PROTECTED]> wrote:
> are there any good crypto tutorials on the eweb
> that cover everything, including all the math
> I can not afford a big book
I honestly don't think you're going to find a single tutorial which
covers every aspect of crypto in depth. It's a fairly diverse field.
Try checking out the notes by Shafi Goldwasser and Mihir Bellare -- go to
http://theory.lcs.mit.edu/ and follow the links to Crypto & Info Security
group, then click on Goldwasser's name to get to her web page.
Ronald Rivest also teaches a course with very good notes, but they were
not presently online last time I checked.
In general, checking out the web pages of ppl who are teaching courses may
yield much useful and free info -- as well as giving you feel for the fact
that there are several different approaches to the subject.
-David
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: Intel 810 chipset security
Date: 1 Aug 1999 21:09:41 -0600
In article <[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>> I would lone to see analysis of that and the PIII ID thingy. has
>> anyone written software yet to emulate the instructions and fake ids
>> yet?
>
>www.bigbrotherinside.com has said that they have already created a program
>that will allow you to randomize your ID (although I am not sure where to
>get it). Intel says that if you turn it off, you cannot reenable the code
>unless you reboot. They found a way around the reboot and did it
>immediatly. It's all a bunch of BS. I personally am running a K-6 400
>mHz, as I suggest everyone else do.
There are sane reasons to want more competition in the market for WINTEL
CPU's that might be enough for you to prefer AMD CPU's. However, the
majority of the BS about the PIII serial number is the uniformed privacy
hysteria. The remainder consists of the silly claims Intel made for
tracking things on the net and for having everyone download programs that
would send PIII ID's. The PIII serial number might conceivably help Intel
chase stolen PIII chips, such as speeding up an audit of an outfit's
systems. Rebooting a 1000 PC's to run a programm that displays the CPU
type (CPUID instruction) and PIII serial number would be a lot faster than
opening 1000 cases. The PIII ID will be handy for "node locking" software
to a system, but it is not vital for that in software written by competent
programmers. (No, I'm not talking about "dongles," given the many sources
of system fingerprints in modern versions of Windows 9* and NT). The PIII
ID does no harm to anyone's privacy, except to increasing the crys of wolf
and the result complacency about the real dangers.
For one example why the PIII serial number is irrelevant to sane privacy
worries, try running guidgen.exe on your Windows system. Notice that the
unique string it generates is unique in the entire universe of boxes
running Windows. Then search the "knowledgebase" at microsoft.com to see
the many places that mechanism is already available, used, and required
to make things work. Even if your programming skills are limited to Visual
BASIC, you can use CoCreateGuid(). Search the microsoft.com for
CoCreateGuid, and notice that CoCreateGuid() is at least implicitly exposed
to Java. If you understand the sources of some of the fingerprint from
CoCreateGuid(), think about JAVA sending the last 6 bytes a GUID.
For another example, run regedit or the newer, more GUI version called
something like regedt2 and search for "id" to see the many strings in your
registry that are are unique to your system, provided you didn't steal
all of the software you have, or if you did, you didn't steal a unique
combination of serial numbered copies.
For yet another example, if you know how to execute arbitrary, unpriviledge
instructions, try the CPUID instruction on any 486 through PII system,
and notice that it provides a good start for a fingerprint of your
hardware.
Almost as bad as the PIII serial number hysteria is that it's victims
imagine that the reason Intel rolled over so quickly is because the alarms
came from knowledgable experts and powerful advocates, instead of because
no one with a technical clue really cares whether the PIII serial number
works.
That the timestamp on the www.bigbrotherinside.com page is "25-Feb-99"
suggests that some of the hysterics finally stumbled on a clue or two.
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To:
talk.politics.crypto,alt.security.ripem,sci.answers,talk.answers,alt.answers,news.answers
Subject: RSA Cryptography Today FAQ (1/1)
Date: 2 Aug 1999 10:12:26 GMT
Reply-To: [EMAIL PROTECTED]
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
------------------------------
From: Krunoslav Leljak <[EMAIL PROTECTED]>
Subject: Re: question: SHA --> stream cipher
Date: 2 Aug 1999 09:11:19 GMT
David Bernier <[EMAIL PROTECTED]> wrote:
: I've read recently in this forum that a secure hash can trivially
: be used to construct a stream cipher. Suppose the secure hash
: function used is SHA-0 or SHA-1. I'd like to know if this is a
: good way to get a stream cipher:
: (0) Choose a secret random IV of 160 bits, say w_0
: (1) Send w_0 securely to recipient [e.g. through public-key algorithm]
: (2) let w_{i+1} = SHA[w_i] for i=0,1,2,3,4...
: (3) The bit-stream [cryptographically strong pseudo-random numbers]
: is then obtained by concatenating w_0, w_1, w_2, ....
Something like this you can find in Bruce Scheiner's: Applied Cryptography;
using one way hash functions as crypting-algo...
There is written that they are weak, however I do not know why ;)))
Maybe that book is good starting point for researching the problem.
Greetings,
Kruno.
------------------------------
From: [EMAIL PROTECTED] (Daniel Vogelheim)
Subject: CFB mode with same initialization vector
Date: Mon, 02 Aug 1999 11:17:55 GMT
Hello group,
why is encryption in CFB mode insecure, if you use the same
initialization vector multiple times?
Applied Cryptography, 2nd ed., says so (chapter 9.6, p.201 middle),
but doesn't explain. I have been unable to figure it out on my own,
and a search turned up nothing. Where can I find a paper eplaining
details?
Any help is greatly appreciated.
Sincerely,
Daniel Vogelheim
------------------------------
From: fungus <[EMAIL PROTECTED]>
Subject: Re: Another random question
Date: Mon, 02 Aug 1999 14:27:24 +0200
Herman Rubin wrote:
>
> >BTW you can get by with say 80 bits of state if your generator is non-
> >linear enough (i.e it takes at least 2^80 steps to learn the seed).
>
> As far as I know, none of the currently proposed PRNGs have anything
> like that much complexity.
How about a 128 bit block cipher in feedback mode?
--
<\___/>
/ O O \
\_____/ FTB.
------------------------------
From: Helger Lipmaa <[EMAIL PROTECTED]>
Subject: Re: Is breaking RSA NP-Complete ?
Date: Mon, 02 Aug 1999 12:19:02 +0000
Scott Fluhrer wrote:
> In article <[EMAIL PROTECTED]>,
> Safuat Hamdy <[EMAIL PROTECTED]> wrote:
>
> >Anton Stiglic <[EMAIL PROTECTED]> writes:
> >
> >> But factoring is still not NP-Complet....
> >
> >Is this what YOU think (or whish) or can you really prove it?
Decision problem corresponding to factoring is not NP-complete unless NP=coNP, an
event generally thought to be untrue. Note that there has been a number of papers
on the possibility of basing cryptography on the assumption
P!=NP. Cf http://philby.ucsd.edu/1998/98-05.html
--
On the possibility of basing Cryptography on the assumption that $P \neq NP$
Oded Goldreich and Shafi Goldwasser
Abstract: Recent works by Ajtai and by Ajtai and Dwork bring to light the old
(general) question of whether it is at all possible to base the security of
cryptosystems on the assumption that $\P\neq\NP$. We discuss this question and in
particular review and extend a two-decade old result of Brassard regarding
this question. Our conclusion is that the question remains open.
Keywords: $\P\neq\NP$, promise problems, smart reductions.
--
And yes, ZP is equal to the union of RP and coRP.
Helger
http://home.cyber.ee/helger
------------------------------
** 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
******************************
