Cryptography-Digest Digest #844, Volume #11 Tue, 23 May 00 14:13:01 EDT
Contents:
My seven encryption books and other crypto literature in my car ... (Markku J.
Saarelainen)
Re: Matrix reduction ([EMAIL PROTECTED])
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Patent state of Elliptic Curve PK systems? (Mike Rosing)
Re: My seven encryption books and other crypto literature in my car ... (Malcolm
Dew-Jones)
Re: how do you know your decyption worked? (Paul Koning)
Re: Graphic Encryption ("Will Critchlow")
Re: Base Encryption: Revolutionary Cypher (wtshaw)
----------------------------------------------------------------------------
From: Markku J. Saarelainen <[EMAIL PROTECTED]>
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.nordic
Subject: My seven encryption books and other crypto literature in my car ...
Date: Tue, 23 May 2000 16:00:37 GMT
Some additional showering methods and techniques ...
You remember my showering technique back in January, 2000 I wrote
about. Basically, just heating half a gallon of water and then using
towels to take a shower with soap. This worked very well. Now here in
Miami, I have operated in the similar ways such as 1. taking a bath or
shower in the ocean or even more creating using public utilities such
as a sink or a toilet to take a shower / clean myself. Actually, some
of these methods work very well and they do not even teach these in the
military. But I practiced many of these techniques back in January,
2000. However, my cooking has not been as creative (I do miss my very
good South Asian Indian meals and desserts) as it would be, if I would
have all cooking facilities, but I have managed to have some good meals
every day. Do you think you could try some of these techniques? And it
is actually me in real.
I do have seven cryptographic and encryption books and other materials
on my back seat. And a lot of other information. In addition, I have
three business suits and several white shirts plus plus hanging just on
the top of my rear seat. So in many ways, I am just a mobile office. It
seems to be my hobby to integrate some military strategies and methods
to my daily life for the purposes of collecting and improving my
intellligence and understanding. Basically, I can change my shorts and
T-shirt to my black businessware within few minutes and again back to
my other clothing.
If I remember correctly James Carwell, the brilliant political
strategist of the Clinton-Gore campaign, did basically live in a car in
1970's or something .. could somebody clarify this? Actually, I think
that he is one very brilliant man.
Yours,
Markku
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Matrix reduction
Date: 23 May 2000 11:45:49 -0400
In article <[EMAIL PROTECTED]>, Chris Card <chriscardN
[EMAIL PROTECTED]> writes:
[Scott Contini writes:]
>> on the recent results, so Peter Montgomery is probably the
>> best person to comment on this. Hopefully he is reading the
>> newsgroup!
Last I heard, Peter was reporting exclusively to microsoft.com -
not sure whether that's the prospective OS.com or the other one.
>Thanks for that info Scott, that's very useful, but it didn't
>actually answer my question :-)
>The (half-baked) idea I had was to get a random linear
>combination of the vectors, score it (= number of non-zero
>elements) and then slighty change the combination looking for
>lower scores, until a local minimum is reached. Repeat until
>local minimum = zero. From the point of view of memory
>usage, this only needs the hold the matrix once + the linear
>combination + a vector recording the elements in the linear
>combination, which doesn't sound too bad. But I've no idea
>how likely this approach is to get a linear dependency, and how
>long it's likely to take.
Since my first two attempts at replying to "Chris Card" off
newsgroup resulted in mail-bounces, and I'm fairly sure that
I'm more interested in Lanczos than he is in "hill-climbing"
(an essential in Montgomery/Murphy polyn selection?), I'll
post this for anyone else that Is interested in how Lanczos
is used in gnfs.
To: Chris Card <[EMAIL PROTECTED]>
RE:
>From: Chris Card <[EMAIL PROTECTED]>
...
>I understand that the matrix reduction step of modern
>factorisation algorithms is usually done using the Block Lanczos
>algorithm (I don't understand the algorithm yet though ...).
>Has anyone looked at the possibility of using hillclimbing
>methods to find a linear dependency in the matrix? I haven't
>given it much thought, but on the face of it there is a large
>solution space with many possible solutions and an obvious metric
>(number of non-zero entries). Or is this complete rubbish? :-)
I'm not familiar with anything other than block Lanczos, but
I wondered what hillclimbing does with the collection of rows
with a given weight? For the RSA-155 matrix, the current hardest
matrix problem solved, there were c. 6.9 million rows/cols, and
the average row density was 67 -- mostly 7 million 0's, with just
67 1's. So, for example, if you needed to do something with the
collection of rows of weight 61, that would be a rather large
set. Guess the other point is that this is all binary; so a
dependency is just a list of rows, and we expect that about half
of the rows are in each dependency. Ie, we're supposed to pick
out 3.5 million of the 7 million rows (for which the columns sum
to 0 mod 2). The current software picks out 16 such dependencies,
half of which give the trivial factorization. Also, it's crucial
in the runtime estimates that the linear algebra is done after omitting
the 10-15 densest columns -- the program only gives psuedo-dependencies
(and there are "character check columns" that improve the likelyhood
that a psuedo-dependency is an actual dependency, an idea of Adleman's,
the "A" of R-S-A). In other words, a method that finds just 3-4
dependencies (after a week of CRAY cputime) wouldn't be sufficient --
I recall having gotten stuck when I'd done something that messed up
half of the dependencies, then finding none of them worked, and having
to re-run (just on an Origin, a small testcase).
Sincerely, B. Dodson, Math Dept, Lehigh Univ.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 16:41:53 GMT
Manuel Pancorbo <[EMAIL PROTECTED]> wrote:
> Opss! Well, I wanted to say the same thing, in a wrong way: we are talking
> of algebra modulo 2^24, aren't we?
We are indeed.
> Let's check the influence of a single bit change. [...] In both cases
> the change in the output bits is only 1 bit.
Yes. That's another good reason for choosing larger matrices. Consider
a top-bit change in one or more of the input words. Multiplying such an
input word by an even number loses the change, beause it shifts off the
top. Multiplying by an odd number doesn't lose the change. This is
good.
Let's look at the matrix mod 2. Let d_ij be the entry at row i, column
j, mod 2. If we change the top bits of x_n for one or more rows n, then
the top bit of output x'_i changes if and only if
---
> d_in = 1 (mod 2)
---
i
The matrix is chosen to have exactly one even number in each row and
column. Thus, any top-bit change to a single input word changes three
output words; a change to two input words changes two output words.
Hmm. I blundered when I was doing my analysis of this stuff. A
three-word difference collapses to a one-word difference after the
multiply. I don't think that makes much of a difference, to be honest
-- it'll be dropped to bit 11, and propagate outwards again from there,
affecting everything in the usual way in a couple more rounds.
Maybe permuting the matrix rows in a key-dependent way would be fun, but
I don't think there's much point. Data space is limited, and the cipher
is more efficient if all the entries are constant and the loop can be
unrolled.
> Do you understand what I mean? Perhaps this is not a serious weakness
> because you make several rounds with the >>12 trick. But take it into
> account anyway.
That's exactly that the linear transformation is there. I already took
this one into account. ;-)
> By the way, why don't you make the matrix key dependent?
Finding invertible matrices over Z_{2^{24}} with good properties is
tricky. Inverting them is tricky too. This all takes up code space and
time, which the DSP doesn't really want to have to do: storin-mktab (the
program which generates the matrix) takes a noticeable amount of time to
run on my PII at home!
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 16:47:02 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> Do you use the term matrix in the sense of mathematics?
Yes.
> If yes, please show in which respect you method differentiate from
> that of Hill.
Maybe I'm remembering wrongly, but I thought the Hill cipher used
multiplication by a secret *key* matrix. The matrix in Storin is
*fixed* and *public*. You can use a different matrix if you like, but
then what you've got isn't my cipher: it's a different and incompatible
one. It's a constant, which provides good diffusion and nonlinearity
for the rest of a block cipher.
If the Hill cipher is the one I think it is, iterating it is pointless
because matrix multiplication is associative. Storin inserts layers of
other transformations between the matrix multiplications to break
everything up and ensure that I'm not wasting my time. The matrix on
its own is not sufficient for security. The other components are there
because they're necessary for the cipher to work well.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 23 May 2000 16:51:42 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> In general linear algebra this is true, but I think modulo addition
> and mult screws it up.
> The matrix in my example is invertible because the determinant is
> non-zero.
Ah. Here's the problem. A nonzero determinant isn't a sufficient
condition for matrix invertibility over Z_n if n isn't prime. ;-)
I'll bet that your determinant is even. Inversion requires a
multiplication by det(M)^{-1}, which doesn't exist in Z_{2^{24}}! The
usual reason a determinant of zero implies a noninvertible matrix is
that division by zero doesn't work. While zero is the only
noninvertible element of any ordinary field, Z_{2^{24}} isn't a proper
field. Extend your condition to require an *invertible* determinant in
the underlying pseudofield and I think you'll find that everything's OK.
-- [mdw]
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Patent state of Elliptic Curve PK systems?
Date: Tue, 23 May 2000 11:56:17 -0500
Roger Schlafly wrote:
>
> Paul Rubin wrote:
> > Are you sure of that? The most interesting ECC variant is ECC over
> > GF(2^n) with optimal normal basis representation, since you can do that
> > in software without any multiplication. But I thought it was patented
> > by Certicom. Is it not? What about ECC over GF(2^n) in general, an
> > obvious method if there ever was one?
>
> Certicom says it has some patent applications pending, but
> it is hard to see how they will stop anyone. Most people
> get better performance in software with other bases, ie,
> trinomial bases. Or one can use (non-optimal) normal bases.
> Or use prime fields where you have more curves and fewer
> known attacks.
Certicom has hardware patents on ONB. There are no software patents on
ONB.
The "all-ones-polynomial" is a cross breed between Type I ONB and
regular
polynomials, it's as fast as trinomials if not quicker. The latter has
been
in the public domain for over a decade. Not well publicized tho :-)
GF(p) will remain more secure than GF(p^n) in any case. If speed is
less important than security, that's definitly a better way to go.
Patience, persistence, truth,
Dr. mike
------------------------------
From: [EMAIL PROTECTED] (Malcolm Dew-Jones)
Crossposted-To: alt.politics.org.cia,soc.culture.russian,soc.culture.nordic
Subject: Re: My seven encryption books and other crypto literature in my car ...
Date: 23 May 2000 10:00:55 -0800
Markku J. Saarelainen ([EMAIL PROTECTED]) wrote:
: Some additional showering methods and techniques ...
: You remember my showering technique back in January, 2000 I wrote
Welcome home, number 5
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: how do you know your decyption worked?
Date: Tue, 23 May 2000 12:16:57 -0400
Carb Unit wrote:
>
> What few FAQs I could find on encryption were way over
> my head. Just explain to me, as if you were talking to
> your mom: How can you decrypt anything if you don't
> know what you're looking for?
>
> I mean, given that most computer files already have one
> level of "encryption" --their respective software's proprietary
> data format, and that there are thousands of such formats
> in the world today, what do you do after you run your decryption
> algorithm? Test if it's a GIF?, no?, a ZIP?, no?, a WAV?, etc?
>
> Or is the assumption always that the material is plain text?
I assume the question you meant to ask is "if I'm attacking
a cipher, trying to break an encrypted message, how do I know
that I succeeded?"
In general, you know because you recover plaintext that matches
what you expect to see. The match can be one of many things:
1. Plain language text (in some plausible language).
2. A valid looking file header for some data file format you
expect to see (like JPG or DOC).
3. The specific plaintext that matches the ciphertext you're
attacking (known plaintext case).
4. Anything that has frequency counts significantly different
from random bytes.
In general you would have *some* notion from context what it
is you can expect. That can be as little as knowing the filetype
(2) or that it's plain language (1). Or it may very well be that
you have the complete matching plaintext (or a partial matching
plaintext).
If you know nothing about the plaintext, and it happens to
be data that looks very similar to random noise (e.g., a JPG file)
life becomes difficult...
---
If you meant to ask "if I'm the intended recipient of a message,
how do I know it hasn't been messed with in transit?" -- the
answer to that is to include a "message authentication code"
such as a keyed hash function.
paul
------------------------------
From: "Will Critchlow" <[EMAIL PROTECTED]>
Subject: Re: Graphic Encryption
Date: Tue, 23 May 2000 18:17:14 +0100
> My encrypted graphic is at:
> http://www.frontiernet.net/~jmb184/cifrgrfx.gif
> The key is at:
> http://www.cl.cam.ac.uk/~fms27/vck/share1.gif
Spoiler space
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Why Halley?
--
========================================
B5 New Court, St. John's College
Cambridge. CB2 1TP
01223 522561
ICQ: 51747953
========================================
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Base Encryption: Revolutionary Cypher
Date: Tue, 23 May 2000 10:45:50 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>
> Some real values have longer expansions in some bases than others.
> Since we're discussing discrete systems intended for cryptography, I
> assume that infinite expansions should not normally be involved.
I will agree with you, but remeber that irrationals, only in one system,
pi, e, etc., may be useful given proper consideration
>
> : Consider that pi can be used as a base having values that can only be
> : approximated in other bases.
>
> Non-integer bases? Surely this is not related to the subject at hand?
OK, I agree to stay with integers, a worthy limited topic in itself.
>
> : Part, an important part, is that there is distingishing differece between
> : bases in efficiency. Also, various manipulations are most awkward in base
> : two [...]
>
> I would usually say the reverse. Computers operate with logic gates, in
> base 2.
>
> If there's an alternative, trying to construct another base on top of this
> on efficiency grounds will usually be a bad move - due to a mismatch with
> the underlying hardware.
Hardware ceases to be te only significant concern because of its current
size and speed. Cipher strength seems always to be a concern however. If
you view encryption as a servo for delivery to the masses, you ignore
their needs.
>
> :> If a systems fails to have proper avalanche properties when viewed from
> :> the perspective of base 2, it's likely to be completely stuffed.
> :
> : You can see the properties you like and have poor properties in another
> : base. [...]
>
> ...but you can't see a failure to get avalanche in *any* base and have
> good overall diffusion properties. If your system exhibits good
> avalanche properties, it should not be possible to transform it into
> another base, and watch the avalanche disappear. If you can do this, the
> system has undesirable cheracteristics in that base.
>
> This is the case Eric was describing. He wasn't seeing avalanche, and
> erroneously concluding that therefore, the effect would happen in all
> bases. He was seeing a /lack/ of avalanche - and concluding that the
> system was broken.
>
> : The point not that bit twiddlers are not doing good things, it is
> : that unless other evaluations are considered, binary constructors can
> : blindsight themselves, never know that this is the case because the fail
> : to look.
>
> A binary construction that demonstrates a lack of avalanche will not
> become invalid if you consider other bases. If there's a significant
> lack of avalanche in base 2, the cypher's bound to be broken.
Tests of avalanche may be faulty because in binary you do not know which
bit was moved to somewhere else, only that it appears to have changed or
not. It means that you have to run a big sample to try to see the trend
as it is. Be sure that statistically the sample is meaningful as best you
can.
It appears that data of higher bases may be harder to analyze, but that
appearance is one that is more obvious, less obvious in base two, but
still there.
>
> FWIW, my view of base changes in cryptography, is that they are
> essentially a diffusion operation. They have minimal confusion
> properties on their own.
One thesis in consideration of base translation is that opportunities for
confusion can be enhanced. If you consider a string of bases that are
involved, even simple tranposition AND substitution are possible at each
base stage. The task is not whether the confusion can be added, but where
and how much do you want to program as reasonable and desired.
Consider a string of bases as an example, ultimate usefulness not a prime
reason for thinking about them: 25/5/2/7/26. Here are the useful
mathematical relationships:
(25^3)=(5^6)<(2^14)<(7^5)<(26^3) or 15625=15625<16384<16807<17576
The application is named Lowa 25, Lowa for obscure reasons, 25 as a sum of
the transpositions is chose to include, 6 penits, 14 bits, and 5 hepits. I
foresee substitutions in both bases 25 and 26. In this example three base
25 characters of plaintext can be encrypted to three base 26 characters.
Multiples would be Lowa 50 and 75, or more. At the 75 level, there would
be nine letter I/O, 18 penits, 42 bits, and 15 hepits. I would just
transpose the lesser information units according to simple permuted keys,
but the design suggests other alternatives.
>
> I am not inclined towards them for several reasons. For one thing, they
> diffuse much better in one direction than in the other - to get
> good "reverse" diffusion, you probably need to reverse and change base
> again. I also prefer small, "atomic" diffusion operations that can be
> interleaved with confusion stages. You generally need to interleave
> diffusion with confusion to prevent the diffusion being undone in a single
> step. Compared to the small, fast operations I prefer, a base-change
> offers better diffusion - but is fatter and slower. Then there's the fact
> that any non-2 prime base has no non-wasteful representation in hardware.
Your thoughts are worth considering, and appropriate. I try to choose
good efficiency in these relationships.
As for speed, these things work pretty fast actually. Such things are good
as a neoclassical method for limited use. Just how much ciphertext is
necessary for definitive analysis, more than you think, lots of blocks,
surely sufficient for small amounts of routine correspondence with
periodic key changes. By definition, they will keep the unskilled at bay,
while the skilled might indeed bray that they might actually contemplate
keeping up all the possibilities attached to just another dumb technique.
> My criticisms are mainly aesthetic - but I take the lack of such
> operations in most existing systems to indicate that others agree.
You can take that agreement is conclusive of ignorance of it as a
primative. As I see that no one has pubically done much in this area
before, be not supprised that Columbus did not find America in an
airplane. My goal is to present more possibilites to the crytogenic stew,
so that diversity can be encouraged, and that security be increased, and
being an analyst means working harder.
As you see, the basis to base translation, more that base conversion,
seems to be closeness, restricted inequalties allowed rather that
equalities demanded. Putting the square peg in the round hole is OK. It's
sort of like people who never can quite match idealistic demands placed on
them. The internal lesson is that lack of perfection does not mean
failure, just that you can use what you have.
Its fun to make some of these rascal algorithms. On the recreational side,
neoclassical methods present new challenges. For instance, the obvious
strategy with base translation algorithms is to attack each shell from the
outside. Finding the limits here will indicate the true nature of the
strength in such options, and the skill of the attacker. Knowing that you
cannot solve a con is simply not any fun.
Can BT be put into more elaborate things? Surely so, a little salt and
pepper to the stew.
--
Secrets that are told or available are not secrets any more, surely
not trade secrets. Security of secrets is no dependant on someone
else's stupidy, only in your making them available in any form.
------------------------------
** 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
******************************
