Cryptography-Digest Digest #956, Volume #10 Sat, 22 Jan 00 20:13:01 EST
Contents:
Re: ADFGVX Construction (Jim Gillogly)
Challenge. ([EMAIL PROTECTED])
Re: What's with transposition? (wtshaw)
Re: Cracking an ADFGVX cipher (wtshaw)
Re: Calculating A^-1 Mod P ("Michael Scott")
Re: Twofish question (ciphertext chaining) (David Wagner)
Re: Does RSA use real prime ? (Frank the_root)
Re: Challenge. (Tom St Denis)
Re: Twofish question (ciphertext chaining) (Hans Petter Jansson)
Re: Intel 810 chipset Random Number Generator ("Trevor Jackson, III")
Re: NIST, AES at RSA conference (John Savard)
Re: Challenge. (John Savard)
Re: NIST, AES at RSA conference ("Trevor Jackson, III")
Re: NIST, AES at RSA conference ("Trevor Jackson, III")
Re: Challenge. (John Savard)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: ADFGVX Construction
Date: Sat, 22 Jan 2000 21:11:47 +0000
UBCHI2 wrote:
> How did the Germans determine the initial ADFGVX checkerboard. Was it based on
> keywords that left some letters in their alphabetical order in the
> checkerboard?
Here's the example from "General Solution for the ADFGVX Cipher System":
A D F G V X
A V I 9 K N G
D 7 S C 3 R O
F W H 8 T E 5
G L A 1 B 2 D
V 4 F 6 J 0 M
X P Q U X Y Z
This is keyed -- note that 1 follows A, 2 follows B and so on.
Callimahos and Friedman (Mil Cryp II vol 2 p. 440-1) say the checkerboard
was a keyword-mixed sequence comprising the 26 letters and 10 digits.
The example they give is comparable to the one above.
--
Jim Gillogly
Trewesday, 1 Solmath S.R. 2000, 21:01
12.19.6.16.1, 4 Imix 9 Muan, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Challenge.
Date: Sat, 22 Jan 2000 21:07:56 GMT
Hi,
Can anyone crack this code?
If you can, email me the solution.
x11yijx24xcydx.ztlyoyaxxzilxmytyuy8x.yuytzoozoozn.zznv
Jack
P.S. It is more for amateurs than professionals with huge computer
power.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: What's with transposition?
Date: Sat, 22 Jan 2000 15:41:38 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> Assuming a "window" of 7 bits. The relative likelihod
> for each possible window position is all that is needed;
> net P=.0000016 for this alignment is compared to the next:
....
> Also note that matching such a short sample isn't very
> reliable, so in practice one would have to juggle several
> of the better column alignments to find the best overall.
Surely with straight ascii you have a cryptographically poor encoding.
Consider that text, even allowing all normal keyboard characters, needs
something like only 94 or 95 characters. Or, you might choose some other
sized set that generally includes the characters that are absolutely
essential. There are many usable choices.
Consider that you were selected a set of 27 characters, the alphabet and
something for spaces. Some allowance and conversion must be used to
handle common punctuation and numbers. Capitalization would not be so
important. The above paragraph might be as follows, as I automatically
handle it anyway:
surel y/wit h/str aight /asci i/you /have /a/cr yptog raphi cally /poor
/enco dingx /cons ider/ that/ textj /even /allo wing/ all/n ormal /keyb
oard/ chara cters j/nee ds/so methi ng/li ke/on ly/ni ne/fo ur/or /nine
/five /char acter sx/or j/you /migh t/cho ose/s ome/o ther/ sized /set/
that/ gener ally/ inclu des/t he/ch aract ers/t hat/a re/ab solut ely/e
ssent ialx/ there /are/ many/ usabl e/cho icesx
The choices are varied as to sets that can match closer to your needs than
pure ascii.
As for transposition, you do have other choices than bits or the 26
alphabet sized information units. The above set has 27 elements, each of
which can be represented by 3 trits (a trit is a base three information
unit). Trits are a different world all together, with a few established
historic algorithms, and a host of new ones.
Consider that for transposition there are things you can do with trits,
like you might with bits or letters, or any other information unit. And,
of course, you may, I already have, use a trit-base transposition scheme
with substitution to produce some interesting results.
If you use ascii as a crutch for input to crypto, you probably also stick
you keys to the computer screen.
Something different: Take 95 character input, and put it directly into 26
characters mathematically. If I simply leave out transposition and
substitution, this sentence changes to this:
nrjxppw texroeo sdmoqzg vveolsr aduwkjf abviidb teitijz wixclos uuojwed
aetneuz viqfeuy wdxjtuv sjxvkad afinnqe abifjil teitijz wixcxde umpzjnp
umpzjre rjdppic adahzec agbesyr uhlcuxg rjwfinf wqtwsih rjhmsfl wcikurk
uotxbxd agbkvpz wjerblu tmfecvc wjcopxa wcauqwr utpravz teirhvn vxblvbc
wjcopya
There is a whole playground of possibilities like this, and better ones.
Note that groups are involved in the above base translation, 5 characters
in the 95 set give 7 in the 26. Believe it or not, it would not by some be
called encryption if optional transposition and/or substitution keys are
not used, as they are listed as defaults for this algorithm called
NagaHills:
Even with these short keys, this is a simple way to get to letters from a
keyboard, and do something traditional with them.
Consider this sentence changed from 97 characters to 26, shuffled in a
Myszkowski by column sequnce to give this resultant ciphertext:
jdljkio suvxvnl ucehtkh dafvicw elbnhzm cugtozt dbknnsi tsjrgkb tzjgczb
axgrsyq ghmoruu smtwlix dffgmin whfsblf hxiauso heevhfs szeejit ggjvdrl
pyhajgq snbwwdu tbdxxrj lcjtidr nufihtr yuywwuj ughlfde smvwind dhjwqfl
Columns = 12: AKEYOFCHOICE; 173984258623
Isn't programming wonderful?
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cracking an ADFGVX cipher
Date: Sat, 22 Jan 2000 15:51:44 -0600
In article <[EMAIL PROTECTED]>, Jim Gillogly <[EMAIL PROTECTED]> wrote:
> It wouldn't be hard to write the code, but executing it is something else.
> There are 36! different checkerboards, assuming no homophony is being used.
> Typical periods used for ADFGVX in the Friedman/Rowlett/Kullback/Sinkov
> paper are up to 27, which means 27! different transposition arrangements,
> for a total of 36! x 27! different things to try in your brute force search.
> That's about 3 x 10^32 x 10^28, or 3 x 10^60. If my calculations are right,
> you're suggesting brute-forcing a 200-bit space.
>
36! x 27! = 138.1 bits + 93.1 = 231.2 bits
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: "Michael Scott" <[EMAIL PROTECTED]>
Subject: Re: Calculating A^-1 Mod P
Date: Sat, 22 Jan 2000 21:24:54 -0000
"Kent Briggs" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Michael Scott wrote:
>
> > An alternative to the Euclidean algorithm.......
> > Mike Scott
>
> I think you meant to say Euler, not Euclid.
>
No, I meant Euclid. Who lived in Alexandria, Egypt, as did Archimedes and
Eratothenes amongst others, as I just found out on an interesting BBC
documentary.
Euler was German (I think)
Mike Scott
> --
> Kent Briggs, [EMAIL PROTECTED]
> Briggs Softworks, http://www.briggsoft.com
>
>
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Twofish question (ciphertext chaining)
Date: 22 Jan 2000 14:38:31 -0800
Four comments on your post:
1. The questions you're asking have nothing to do with Twofish and
everything to do with chaining modes. They'll apply equally to any other
block cipher.
2. You should distinguish between 8-bit CFB mode and 128-bit CFB mode.
They're different. You seem to be using 8-bit CFB mode.
3. A potential solution for your application is to use the block cipher in
a standard stream encryption mode, e.g., counter mode or OFB mode, taking 8
bits from the stream at a time. This will be fast, with no data expansion.
Does it do what you want? If so, use it -- it's standard and well-understood.
4. I couldn't understand your proposal. What do you mean by "permute",
"cycle", "IV", etc.? Can you write it in a more formal or precise notation?
------------------------------
From: Frank the_root <[EMAIL PROTECTED]>
Subject: Re: Does RSA use real prime ?
Date: Sat, 22 Jan 2000 22:47:42 GMT
Hi,
Tom St Denis wrote into my screen:
> Yes it's true. Factoring a large N bit number will take too long for
> most cases.
How EXACTLY, RSA choose p and q? Does anyone have a good article about
that? I heard about a good method to find larges primes: First, I
determine the lenght of p and p ( in bits ) and then, I generate a
approximation of the rank of the smallest/greatest primes numbers in
this range knowning that numbers of primes not exceding a abitrary
number c is asymptoticly equal to "c � ln c".
a = 2^lenght � ln 2^lenght
b = 2^(lenght-1) � 2^(lenght-1)
After, I choose randomly an other number "c" in the range ]a,b[. Then I
start searching a prime number around "c*ln c". Repeat untils two primes
are found...
Is this the way RSA proceed?
> ... So they use probable primality testers. ...
How those primaly tester works?
> 2^51. Even if they are composite the chances that you decrypt/encrypt
> messages sucessfully more then once is way smaller.
And I also heard that if p and p are not primes, n will be factorised
very quickly.
> See the decryption exponent 'e' is found by taking d^-1 mod (p-1)(q-
> 1). If either q or p are not prime then 'e' will not be the inverse
> exponent mod pq.
I don't understand this one very well. Are you talking about the "ed mod
Phi(n) = 1" relation? What is the link between this and the obscure
notation "d = e^-1 mod ( Phi(n) )"? Why there is a exponent? And, does
anyone know where a mathematic demonstration of RSA is aviaible? I mean,
WHY IT WORKS. On the net, I only found pages explaining the algorithm
himself. Tanks.
Frank
--
Ceux qui r�vent le jour, savent des choses qu'ignorent ceux qui r�vent
la nuit.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Challenge.
Date: Sat, 22 Jan 2000 22:35:26 GMT
In article <86d674$coa$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Hi,
>
> Can anyone crack this code?
> If you can, email me the solution.
>
> x11yijx24xcydx.ztlyoyaxxzilxmytyuy8x.yuytzoozoozn.zznv
>
> Jack
>
> P.S. It is more for amateurs than professionals with huge computer
> power.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
What possess people to post 'break this "rigtyh3g9gtrb34uotufhjwr"' is
beyond me.
TAKE A HINT WE DONT GIVE A FLYING RATS ASS ABOUT YOUR STUPID RANDOM
TEXT.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Hans Petter Jansson)
Subject: Re: Twofish question (ciphertext chaining)
Date: 22 Jan 2000 23:35:16 GMT
> 1. The questions you're asking have nothing to do with Twofish and
> everything to do with chaining modes. They'll apply equally to any other
> block cipher.
Good. I supplied the cipher type more as peripheral information, being unsure
of its influence on the total equation. Better safe than sorry.
> 2. You should distinguish between 8-bit CFB mode and 128-bit CFB mode.
> They're different. You seem to be using 8-bit CFB mode.
Correct.
> 3. A potential solution for your application is to use the block cipher in
> a standard stream encryption mode, e.g., counter mode or OFB mode, taking 8
> bits from the stream at a time. This will be fast, with no data expansion.
> Does it do what you want? If so, use it -- it's standard and well-understood.
Thanks. After reading this, I understood that OFB mode does what I want. It
is actually congruent with the proposal I was trying to make, and I prefer
standard and well-understood algorithms when available.
> 4. I couldn't understand your proposal. What do you mean by "permute",
> "cycle", "IV", etc.? Can you write it in a more formal or precise notation?
My apologies. I'm not a cryptanalyst, but I try to stay within the
terminology used by Schneier.
IV is the initialization vector for the cipher's internal state when used in
chaining modes (Applied Cryptography, p. 194), a) "permute" and b) "cycle"
can be regarded as layman's terms for a) doing one run of the next-state
function and b) encrypting a series of bits using the data corresponding to
the resulting internal state.
With that said, I withdraw my question, as you've provided a sufficient
answer. Thanks again.
-- HP
------------------------------
Date: Sat, 22 Jan 2000 19:02:16 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Intel 810 chipset Random Number Generator
Michael Sierchio wrote:
> "Trevor Jackson, III" wrote:
>
> > Thank you for the reference. The mood of this paper makes me want to
> > ask who paid for the study.
>
> It says quite plainly that it was Intel -- however,
I looked, but I must have missed it.
> Paul Kocher is
> a talented and reliable cryptanalyst. Cryptography Research does a
> lot of this sort of consulting, I'm sure the fee is the same whether
> Intel likes the results of the study or not ;-)
I'm sure Intel liked it. The puff-to-fact ratio is middling high.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: NIST, AES at RSA conference
Date: Sat, 22 Jan 2000 23:43:59 GMT
On Sat, 22 Jan 2000 20:47:09 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>"Unlikely?"
I should have been more explicit. I felt it was unlikely that a
(modest) amount of money could have obtained better analysis of these
ciphers in the short term.
If one offers enough money that professors might leave their posts to
work full time on the project, or
>A dedicated group of good -- but not necessarily world-class -- minds
>*can* make world-class progress, especially if well-organized,
>well-funded, and well-motivated.
if one is going to use time as well as money, and train your own
people, yes, I can't deny that results could be achieved then.
>It is all very fine to get a few weeks of free work from crypto gods,
>but real progress is often made bit-by-bit and day-by-day with the
>unrelenting long-term effort of a well-funded task force made up of
>many minds. We should not be asking for more crypto-gods; we should
>instead be funding crypto R&D and -- like magic! -- new crypto-gods
>will appear.
Unfortunately, the market fails to percieve a pressing need for
fundamentally better ciphers than the ones we already have.
One has the alternative of leaving things to the free market, or
asking for some kind of intervention in the free market: such as
having the government fund research on drugs that for some reason are
unprofitable to pharmaceutical companies, or having the government pay
to land men and women on Mars.
An ordinary person can help to change what the government does by
voting or writing his Congressman. But I do not know how one goes
about changing what the marketplace does (well, I suppose people have
taken out ads talking about what catching tuna used to do to
dolphins...) - individual choices in the market, unlike in politics,
are just individual choices, without a multiplier effect.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Challenge.
Date: Sat, 22 Jan 2000 23:46:44 GMT
On Sat, 22 Jan 2000 22:35:26 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote, in part:
>TAKE A HINT
Normally, I'd agree with the sentiment, but if the postscript is true,
that this is a "puzzle for amateurs", then, even if to the wrong
newsgroup, something useful has been contributed.
Had this been a new "unbreakable" cipher, of sufficient complexity
that it was, say, even comparable to 4-round DES, then of course it
would be a total waste of time.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
Date: Sat, 22 Jan 2000 19:22:19 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
John Savard wrote:
> [EMAIL PROTECTED] (Terry Ritter) wrote, in part:
> >On Thu, 20 Jan 2000 07:41:14 GMT, in <866e6o$i0e$[EMAIL PROTECTED]>, in
> >sci.crypt Hammer <[EMAIL PROTECTED]> wrote:
>
> >>One of the interesting things I took from the talk was, in my opinion,
> >>they are nearly BEGGING for cryptanalysis of the AES finalists.
>
> >First of all, *OF* *COURSE* they are *begging* for cryptanalysis; they
> >certainly are not *paying* anything!
>
> >It was first of all wrong and secondly unwise to base the future of a
> >networked society on ciphers acquired by begging and contribution.
>
> Without getting into that specific question here, I might note that
> there is a very limited number of mathematicians in the academic
> community specializing in cryptography-related matters. A goodly
> proportion of them have involved themselves with the AES effort in
> some way or other.
>
> Aside from the results so far achieved against some of the candidates
> that did not become finalists, however, I'm not surprised that, given
> the current state of our knowledge, little useful can be done to show
> weaknesses in the AES finalists. As Bruce Schneier noted, they're all
> submitted by teams which include some of the world's top cryptanalysts
> in the open community, so it's hardly surprising they don't have
> weaknesses that even their colleagues could easily find.
>
> Whether NIST puts some money on the table or not, they're not suddenly
> going to turn up a rock, and find under it cryptanalysts whose
> expertise is decades ahead of those who have already subjected the AES
> candidates to the scrutiny that, so far, has had little to say about
> the finalists. Leaving out of consideration the rock marked "NSA", of
> course.
While this is true I believe it neglects a fundamental incentive which is
amplified by the lack of remuneration for AES candidate evaluation. If we
assume that the leading cryptographers are a small set of individuals, then
that set is partitioned into those who have an interest in a particular AES
candidate and those who are objective about the candidates. (That is an
observation about incentives not motives; it is not intended to insult or
denigrate anyone).
Those who have an interest in a particular candidate have a complementary
interest in all of the other candidates. It is in their interest to pursue
any perception of weakness in the other candidates in order to further their
own candidate. This interest is high prior to the final selection and much
lower thereafter.
Those who have no interest in an AES candidate may have perceptions of
weakness but, as has been pointed out, there is some, but probably not an
exciting incentive to attacking an AES candidate. However, after the final
selection their interest in following up any
hints/hunches/perceptions/theories of weakness in the AES selectees will be
dramatically heightened. The payoff for breaking an AES selectee is
presumable much larger than the payoff in breaking an AES candidate.
>
>
> Also, given the general Administration climate on encryption issues,
> it is hardly surprising that NIST was not permitted to spend much in
> the way of public funds on an effort that is, to put it mildly,
> swimming somewhat against that current.
Interesting observation. Since the fat lady hasn't sung yet, the
Administration's influence still has a window of opportunity to influence
events. I do not perceive this as a particularly strong threat because the
clueless probably wouldn't be able to determine what decisions would further
their ends.
------------------------------
Date: Sat, 22 Jan 2000 19:29:03 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: NIST, AES at RSA conference
Nicol So wrote:
> Serge Vaudenay wrote:
> >
> > The AES process is the only standardization process where
> > cryptanalysts work for free.
>
> I don't see anything wrong with that. I'm not aware of any standards
> activities in which participants are paid for their participation. Most
> often, the individuals attending standards meeting are paid by their
> employers, who *are* the real participants. The participating
> organizations absorb the travel expenses of their own employees and
> sometimes sponsor the meetings. If you are a self-employed consultant,
> then you don't get paid, period. Of course, the participants believe
> that the standards will somehow benefit themselves, but standards often
> benefit many more parties than just the participants, and they don't
> seem to mind.
>
> Think about it, people do unpaid charity work every day, and most of
> these good-hearted individuals don't get any special recognition.
> Those who don't feel like participating simply don't. You can think of
> participating in the AES process as public service. If you don't feel
> like participating, just let other volunteers do it.
>
> > They get no honorarium and no publication.
>
> In my opinion, the prestige associated with being a co-designer of the
> AES cipher is worth a lot more than any honorarium you can reasonably
> expect to get. As for the part of not getting a publication out of the
> effort, I'm not sure about it. If, in the process of cryptanalyzing the
> candidate ciphers, you discover a new cryptanalytic technique, you can
> always try to turn it into a journal paper (or at least a conference
> paper). Does the AES process require you to publish your results in a
> way that gives you no publication credit?
>
> > If you think about previous "analysis" of the
> > 10 rejected candidates, there are seldom real significant attacks and
> > most of them are indeed quite secure.
>
> Unless you want to allow multiple winners, which would reduce
> interoperability, it is quite unavoidable that some high-quality
> candidates don't get chosen. Situations like this exist in real life,
> and people seem to accept it. In an election for a public office, it
> doesn't matter that two candidates are comparable in many ways, only one
> will be chosen for the office.
>
> > Actually, if an expert do not have any personal interest about AES, he
> > should better wait
> > for the final standard before doing some substantial work. In the
> > meanwhile he can work
> > for other standards.
>
> I honestly cannot make the above recommendation. If anyone believes that
> it is important that the "best" candidate be chosen as the winner, and
> that he is in a position to help make that happen, he should contribute
> his analytic efforts while the winner is still being chosen, not
> afterward.
The word "should" implies a moral imperative. Given that the payoff to a
researcher may be far larger after the selection than before, the good of
society will be in conflict with the good of the researcher. Altruism is
highly prized because it is both expensive and rare. It is unreasonable by
inspection to expect serious professionals to perform hard, and by your
criteria important, work for nothing.
>
>
> --
> Nicol So, CISSP // paranoid 'at' engineer 'dot' com
> Disclaimer: Views expressed here are casual comments and should
> not be relied upon as the basis for decisions of consequence.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Challenge.
Date: Sun, 23 Jan 2000 00:48:48 GMT
On Sat, 22 Jan 2000 22:35:26 GMT, Tom St Denis <[EMAIL PROTECTED]>
wrote, in part:
>TAKE A HINT
Normally, I'd agree with the sentiment, but if the postscript is true,
that this is a "puzzle for amateurs", then, even if to the wrong
newsgroup, something useful has been contributed.
Had this been a new "unbreakable" cipher, of sufficient complexity
that it was, say, even comparable to 4-round DES, then of course it
would be a total waste of time.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/index.html
------------------------------
** 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
******************************
