Cryptography-Digest Digest #363, Volume #13 Tue, 19 Dec 00 06:13:00 EST
Contents:
Re: Encrypting messages in images?? (AllanW)
Re: Q: Result of an old thread? (Bryan Olson)
use of position of characters for encryption ("lowtus")
Re: Q: Result of an old thread? (Benjamin Goldberg)
Re: Q: Result of an old thread? (Benjamin Goldberg)
Re: Nonlinearity question (Benjamin Goldberg)
Re: Mathematical concepts (Paul Rubin)
Re: Q: Result of an old thread? (Bryan Olson)
test ("Pahenty")
RE: Q: Result of an old thread? (Bryan Olson)
Re: test failed (Simon Best)
Re: Q: Result of an old thread? (Simon Best)
Re: Why primes? (Jorgen Hedlund)
Re: Nonlinearity question (Benjamin Goldberg)
Re: Use of multiplexing (Mok-Kong Shen)
Re: Result of an old thread? ("Jakob Jonsson")
Re: Result of an old thread? (Mok-Kong Shen)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Re: Q: Result of an old thread? (Mok-Kong Shen)
Re: Nonlinearity question (Mok-Kong Shen)
Re: Result of an old thread? (Benjamin Goldberg)
----------------------------------------------------------------------------
From: AllanW <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.security
Subject: Re: Encrypting messages in images??
Date: Tue, 19 Dec 2000 02:20:14 GMT
"Lester Burnam" <[EMAIL PROTECTED]> wrote:
> > http://www.innovatools.com/software/isecrets/index.htm
> > (free download version). Can be quite useful !!!
>
> well i want to know why this program tries to call home?
> anybody know why??
> outbound attempted for (IPC SERVER
> C:\WINDOWS\SYSTEM\MSIPCSV.EXE
> ans2.adsoftware.com)
>
> i blocked it of course. so why does it need to call
> home? seems like a nice program but with it
> calling home i decided no thanks and uninstalled it.
Lester, did you READ the download site, before you downloaded
it and installed it? I've read the web site even though I have
NOT (yet) downloaded the program, and I know enough to answer
your question.
The free version is advertiser-supported. It's going to
download some advertising to show you while you use the
program. The web site name (ans2.adsoftware.com) should
also have given you a clue.
You can upgrade to a functionally-identical version of the
program, without any advertising, for $19.95. Check out the
same web site.
And please, from now on, never download anything --
especially anything free -- without first reading about what
it is you're getting. Or, at least, don't complain about
getting something you didn't expect when you have no idea
what to expect.
(Learn to use the Shift key, too! :-)
--
[EMAIL PROTECTED] is a "Spam Magnet," never read.
Please reply in newsgroups only, sorry.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 02:21:03 GMT
Mok-Kong Shen wrote:
> Bryan Olson wrote:
> > If AS is n by n with rank m < n, then you can express AS as
> > an n by m times an m by n. Call then C and D respectively.
> > There exists some S' such that S = S'*D. After the second
> > pass solve for D*B instead of B. In the third pass we get
> > S'*D*B with D and D*B known and S = S'*D.
>
> I don't think that the above constitute a proof of either
> a one-shot getting of S or with only very few trials. We
> need a clear proof, don't we? (Same as we need a proof of the
> amount of work to crack a cipher or termination/non-termination
> of some process.) In particular I don't yet understand
> your first sentence.
Then you'd have no idea whether "the above constitutes a
proof" or not would you?
The nice thing about the previous solution is that it doesn't
require as much background. You would have found that it
efficiently recovers the secret if you'd bothered to try.
"Rank" will probably be a few chapters into an introductory
linear algebra text.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "lowtus" <[EMAIL PROTECTED]>
Subject: use of position of characters for encryption
Date: Mon, 18 Dec 2000 22:45:56 -0600
Reply-To: [EMAIL PROTECTED]
Would it be better or worse to use a system in
which the ciphertext is created based on the
location of a particular character?
For example:
f(x) = (position(x) + x) * key
position(x) = x'th character in plaintext.
x = character
I think that implementing this would
destroy the ability to use a type of trans-
position, but which one is better?
That, up there, or transposition?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 04:54:21 GMT
Bryan Olson wrote:
>
> Benjamin Goldberg wrote:
> [...]
> > Another interesting thing to point out is... if S is created by
> > multiplying more than one matrix together, and one of those factors
> > is singular, the result is also singular. With the scheme you
> > described, the opponent can know that he has S because there's a
> > column of 0s.
> > If S is instead the product of matrices, it can be made so that
> > there's no 0 column, and we can still be sure it's singular -- thus
> > making it slightly harder for an opponent to test that his answer is
> > correct.
>
> Useless. The scheme is trivial either way.
You have proof that the scheme is trivial?
I'd like to see it.
Especially since the thread which started the debate left some things
ambiguous -- the size of A,B and S, and the field in which the
operations were done.
Show me a general method of breaking the scheme, where A, B, and S are
4x4 matrices, and their elements are drawn from GF(2**32). A and B are
randomly chosen from the set of all invertable 4x4 GF(2**32) matrices in
an unbiased way. S is the product of S0 and R, where S0 has the first
column as all 0s, and the other elements random, and all elements of R
are random.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 04:59:19 GMT
Simon Best wrote:
[snip]
> This method can be applied to larger matrices. The important thing is
> that the empty columns of S just end up effectively discarding rows of
> B and other matrices, such that the whole thing's equivalent to not
> bothering with empty columns in S in the first place. Those empty
> columns don't add any security after all, and the system is trivially
> defeated.
>
> So, is there any reason why this method would not work?
None at all, which is why choosing S to simply have a 0s column is a
poor way of making it singular. It would be slightly better to chose S
using the method I described, and *much* better to choose it in an
unbiased way from all singular matrices which have no al-0s row or
column.
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Nonlinearity question
Date: Tue, 19 Dec 2000 05:05:58 GMT
Mok-Kong Shen wrote:
>
> Benjamin Goldberg wrote:
> >
> [snip]
> > Right, which is why I suggested it. As Mok wrote, the only problem
> > is a practical one, though certainly not the way he implied. Only
> > an utter madman would try implement a 128x128 sbox as a lookup
> > table. Calculating the inverse under the polynomial modulo would be
> > done as a function, *not* a table. The practical problem is that of
> > speed, not space. Inversion doesn't use that much memory, but it's
> > not very fast, and its possible that there might be timing attacks
> > on it.
>
> The issue is probably not clear-cut without actual
> investigation. While the speed of doing GF computations
> for 128 bit S-box is lower, one might be able to reduce
> the number of rounds needed, I guess. There is a trade-off.
> But, unless there is a theoretical proof, the quality of
> the S-boxes has to be verified through computation in
> any case.
True enough... but how do I verify the quality of a 128x128
substitution?
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Mathematical concepts
Date: 18 Dec 2000 21:26:39 -0800
"Joris Vankerschaver" <[EMAIL PROTECTED]> writes:
> Thank you all for your swift responses! As for which book to buy, I think I'll
> settle for the Henri Cohen book. It looks like something I haven't seen
> before :)
Better look at it before you buy it. It is a graduate level text.
If you've just had some undergraduate courses in algebra and number
theory, Cohen's book will be very difficult. But it is a great book.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 06:14:33 GMT
Benjamin Goldberg wrote:
> Bryan Olson wrote:
> > Useless. The scheme is trivial either way.
>
> You have proof that the scheme is trivial?
> I'd like to see it.
The efficient method to recover S proves it's trivial.
> Especially since the thread which started the debate left some things
> ambiguous -- the size of A,B and S, and the field in which the
> operations were done.
It required taking inverses, so the operations in the field
are tractable. That's all we need.
> Show me a general method of breaking the scheme, where A, B,
> and S are 4x4 matrices, and their elements are drawn from
> GF(2**32). A and B are randomly chosen from the set of all
> invertable 4x4 GF(2**32) matrices in an unbiased way. S is
> the product of S0 and R, where S0 has the first column as
> all 0s, and the other elements random, and all elements of R
> are random.
Already done. You didn't try it did you?
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: "Pahenty" <[EMAIL PROTECTED]>
Subject: test
Date: Tue, 19 Dec 2000 12:19:37 +0600
test
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: RE: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 06:23:37 GMT
"Manuel Pancorbo" wrote:
>
> "Walter Hofmann" wrote:
> > You don't need p,q to do any of the computations above.
> >
>
> Alice needs p,q to compute A^-1, because (det A)^-1 mod N is needed.
The usual general procedure for computing the inverse
doesn't use the inverse of the determinate. If we do need
the mod N inverse that's no problem; mod N inverses are easy
to compute without knowing the factors of N.
--Bryan
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: test failed
Date: Tue, 19 Dec 2000 07:55:46 +0000
Pahenty wrote:
>
> test
Your test seems to have failed, as the body's been replace with a
duplicate of the subject.
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 08:09:40 +0000
Benjamin Goldberg wrote:
>
> Simon Best wrote:
> [snip]
> > This method can be applied to larger matrices. The important thing is
> > that the empty columns of S just end up effectively discarding rows of
> > B and other matrices, such that the whole thing's equivalent to not
> > bothering with empty columns in S in the first place. Those empty
> > columns don't add any security after all, and the system is trivially
> > defeated.
> >
> > So, is there any reason why this method would not work?
>
> None at all, which is why choosing S to simply have a 0s column is a
> poor way of making it singular. It would be slightly better to chose S
> using the method I described, and *much* better to choose it in an
> unbiased way from all singular matrices which have no al-0s row or
> column.
And for my next trick... I will have to revise matrices (I didn't
realise I was so rusty with'em!).
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
From: Jorgen Hedlund <[EMAIL PROTECTED]>
Subject: Re: Why primes?
Date: Tue, 19 Dec 2000 09:46:23 +0100
Reply-To: [EMAIL PROTECTED]
Jorgen Hedlund wrote:
>
> [snip]
>
I truly appreciate your replies. Thanx!
The replies has given me something with
substance to work with. I will have to
use a pen and paper for a while, trying
to see, for myself, what you're explaining.
For instance, I'll have to prove for
myself everything, otherwise it might
be difficult to understand the true
nature of what's happening with the
numbers..
I do own a crypto book (or two if one
counts the Code Book), however I find
it really difficult to understand, since
its theroetical approach to everything.
I'm a philosopher and a programmer, that
leaves that I'm no mathematician, which
apparently is more or less required in
crypto science.
I'll get back in a while with some new
ideas, but do sleep some until then.. ;)
BR/jh
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Nonlinearity question
Date: Tue, 19 Dec 2000 08:54:15 GMT
Hmm, I just discovered that Tom Denis's TC3 implements this very idea.
I suppose for analysis I'll just wait for his paper :)
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Use of multiplexing
Date: Tue, 19 Dec 2000 10:25:14 +0100
Simon Best wrote:
>
> Um, do you mean 'user level' in the Unix sense of servers running as
> user level processes?
Well, I orignally used 'application level'. This is in the
sense of OSI model.
M. K. Shen
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 10:44:27 +0100
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in the message
news:[EMAIL PROTECTED]...
>
>
> Jakob Jonsson wrote:
> >
> > The scheme is insecure because there is only one solution S:
Sorry, I meant that the scheme is insecure because the solution is easy to
find. There is only one solution since there is no shared secret.
> > Put
> >
> > X = AS,
> > Y = SB,
> > Z = ASB.
> >
> > To determine S, find any nonsingular W such that
> >
> > X*W = Z (i.e., ASW = ASB).
> >
> > [This is an equation system with n^2 equations and n^2 variables (all
> > elements in W), but the equations are dependent since X is singular, so
we
> > will have many solutions.]
>
> Sorry for my ignorance. How do you 'algorithmically'
> determine a nonsinglular W? (Or do you have to depend on
> your luck?) Since X is singular, the Gaussian elimination
> process operating on X will get stuck before reaching the
> last row, if I don't err.
All solutions can be found efficiently via Gaussian elimination in the usual
manner. We won't get stuck. Instead we will get a bunch of zero rows in the
matrix X, and since there are solutions to the equation X*W = Z, the
corresponding rows in Z will be zero as well. Just drop these rows and solve
the remaining system. You will obtain some parameters (one parameter in each
column of W for each zero row in X after Gaussian elimination) in your
solution. For example, with two zero rows in a 4x4 matrix system, the
solution in one column of W will be something like
w_1 = a s + b t + c
w_2 = d s + e t + f
w_3 = s
w_4 = t,
where s and t are parameters and a,b,c,d,e,f are known constants. Any values
on s and t will give a solution.
To find a nonsingular matrix you will have to guess, but in GF(q) the
probability that a random nxn matrix is nonsingular is quite high, at least
0.28 for q=2, higher for larger q, and close to 1 for very large q (*), so
if you simply choose parameters at random, you will find a nonsingular
matrix pretty soon.
Jakob
(*) The number of nonsingular nxn matrices in GF(q) is
(q^n-1)*(q^n-q)*(q^n-q^2)*...*(q^n-q^{n-1}). To get the fraction P of
nonsingular matrices, divide each factor with q^n and compute the log of the
result. You obtain
log(P) = log(1-1/q) + log(1-1/q^2) + log(1-1/q^3) + ...
Now approximate.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 11:26:09 +0100
Jakob Jonsson wrote:
>
[snip]
> To find a nonsingular matrix you will have to guess, but in GF(q) the
> probability that a random nxn matrix is nonsingular is quite high, at least
> 0.28 for q=2, higher for larger q, and close to 1 for very large q (*), so
> if you simply choose parameters at random, you will find a nonsingular
> matrix pretty soon.
>
> (*) The number of nonsingular nxn matrices in GF(q) is
> (q^n-1)*(q^n-q)*(q^n-q^2)*...*(q^n-q^{n-1}). To get the fraction P of
> nonsingular matrices, divide each factor with q^n and compute the log of the
> result. You obtain
>
> log(P) = log(1-1/q) + log(1-1/q^2) + log(1-1/q^3) + ...
>
> Now approximate.
But we don't have a 'random' matrix in the full sense,
i.e. the elements are partly related to one another
due to the Gaussion method ('the parameters') isn't it?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 11:25:52 +0100
Simon Best wrote:
>
> Mok-Kong Shen wrote:
> >
> > Bryan Olson wrote:
> [...]
> > > Your "just knowing..." quote seems to be in _favor_ of long
> > > searches. Did you mean it would _not_ solve the problem? Why
> > > would you think the searches are long? All you need are
> > > linearly independent vectors. And this is just for an answer
> > > that we can plug into Simon Best's solution which requires an
> > > invertible B'.
> > >
> > > If AS is n by n with rank m < n, then you can express AS as
> > > an n by m times an m by n. Call then C and D respectively.
> > > There exists some S' such that S = S'*D. After the second
> > > pass solve for D*B instead of B. In the third pass we get
> > > S'*D*B with D and D*B known and S = S'*D.
> >
> > I don't think that the above constitute a proof of either
> > a one-shot getting of S or with only very few trials. We
> > need a clear proof, don't we?
>
> I disagree. A clear proof of insecurity in the suggested system isn't
> necessary. What is necessary is either a proof that the suggested
> security system in secure (like with the one-time pad), or an exposition
> of what the security is founded upon (like how RSA is based on the
> factoring problem).
>
> At the moment, it seems that the security is supposed to rely on
> difficulties with effectively 'dividing' matrices when one or more is
> singular. (Okay, I know, there's no such thing as matrix division, but
> I'm sure you all know what I mean in this context.)
>
> > (Same as we need a proof of the amount of work to crack a cipher or
> > termination/non-termination of some process.)
>
> I don't think I've seen any proof at all of the amount of work to break
> the suggested cipher. How much work is it supposed to take? Is it
> supposed to be brute force? Brute forcing what? Brute forcing A? B?
> AS?
You misunderstood me. The cipher in question has never
been formally analysed, otherwise we wouldn't be discussing
it here. I was alluding to the analogy of block ciphers,
where a neat claim of its strength/weakness needs to give
the quantity of amount of work to break it with respect
to a given technique.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 11:26:03 +0100
Simon Best wrote:
>
> (I'll mention here that I'll use multiplications to get relevant
> results, rather than inversions with multiplications, as the
> multiplications are enough to show it, and I'm too rusty on inversions!)
>
> S = A = B=
> [ S0,0 0 ] [ A0,0 A0,1 ] [ B0,0 B0,1 ]
> [ S1,0 0 ] [ A1,0 A1,1 ] [ B1,0 B1,1 ]
>
> So...
>
> AS =
> [ A0,0 A0,1 ][ S0,0 0 ]
> [ A1,0 A1,1 ][ S1,0 0 ]
> =
> [ (A0,0)(S0,0)+(A0,1)(S1,0) 0 ]
> [ (A1,0)(S0,0)+(A1,1)(S1,0) 0 ]
>
> which I'll type as:
>
> AS =
> [ AS0,0 0 ]
> [ AS1,0 0 ]
>
> for the time being.
>
> Then...
>
> ASB =
> [ AS0,0 0 ][ B0,0 B0,1 ]
> [ AS1,0 0 ][ B1,0 B1,1 ]
> =
> [ (AS0,0)(B0,0) (AS0,0)(B0,1) ]
> [ (AS1,0)(B0,0) (AS1,0)(B0,1) ]
>
> Notice that ASB is independent of B1,0 and B1,1! The second row of B
> plays no part in producing ASB. This is very important, as this is the
> only opportunity B gets to add its elements to the encryption, but its
> bottom row plays no part. What's more, if we define:
>
> AS' = B' =
> [ AS0,0 ] [ B0,0 B0,1 ]
> [ AS1,0 ]
>
> by chopping out the empty column of AS and the corresponding row of B,
> then we can do:
>
> ASB' =
> [ AS0,0 ][ B0,0 B0,1 ]
> [ AS1,0 ]
> =
> [ (AS0,0)(B0,0) (AS0,0)(B0,1) ]
> [ (AS1,0)(B0,0) (AS1,0)(B0,1) ]
> = ASB
>
> Let's now consider some matrix S', which is identical to S except that
> it's got the empty columns left out:
>
> S' = A =
> [ S0,0 ] [ A0,0 A0,1 ]
> [ S1,0 ] [ A1,0 A1,1 ]
>
> A(S') =
> [ (A0,0)(S0,0)+(A0,1)(S1,0) ]
> [ (A1,0)(S0,0)+(A1,1)(S1,0) ]
> =
> [ AS0,0 ]
> [ AS1,0 ]
> = AS'
>
> So, the AS' that I've trivially obtained from AS is what AS would have
> been if S had not had those empty columns in in the first place.
> Furthermore, my ASB' is what ASB would have been if B had not included
> the rows discarded by the empty columns in AS.
>
> The important thing here is that AS' is invertible, and can trivially be
> used to derive a matrix B'. B' will just be B without the discarded
> rows. Is that enough to get S from SB? Looking at SB in terms of S and
> B:
>
> S = B =
> [ S0,0 0 ] [ B0,0 B0,1 ]
> [ S1,0 0 ] [ B1,0 B1,1 ]
>
> SB =
> [ (S0,0)(B0,0) (S0,0)(B0,1) ]
> [ (S1,0)(B0,0) (S1,0)(B0,1) ]
>
> Again, the bottom row of B is discarded. Comparing with using B':
>
> S' = B' =
> [ S0,0 ] [ B0,0 B0,1 ]
> [ S1,0 ]
>
> S'B' =
> [ (S0,0)(B0,0) (S0,0)(B0,1) ]
> [ (S1,0)(B0,0) (S1,0)(B0,1) ]
> = SB
>
> Now, is B' invertible? It certainly looks like it! Can the inverse of
> B' be used with SB to get S? It's certainly looking that way! After
> all, SB is both the product of S with B and S' with B', and S' contains
> the whole message!
>
> This method can be applied to larger matrices. The important thing is
> that the empty columns of S just end up effectively discarding rows of B
> and other matrices, such that the whole thing's equivalent to not
> bothering with empty columns in S in the first place. Those empty
> columns don't add any security after all, and the system is trivially
> defeated.
>
> So, is there any reason why this method would not work?
Sorry, I have difficulty to follow you. Your AS' is a
vector not a matrix. How can that be invertible? And
the (trivial) derivation of B' is also not given, I
suppose. Could you work out a numerical example? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Tue, 19 Dec 2000 11:25:57 +0100
Bryan Olson wrote:
>
> Mok-Kong Shen wrote:
> > Bryan Olson wrote:
> > > If AS is n by n with rank m < n, then you can express AS as
> > > an n by m times an m by n. Call then C and D respectively.
> > > There exists some S' such that S = S'*D. After the second
> > > pass solve for D*B instead of B. In the third pass we get
> > > S'*D*B with D and D*B known and S = S'*D.
> >
> > I don't think that the above constitute a proof of either
> > a one-shot getting of S or with only very few trials. We
> > need a clear proof, don't we? (Same as we need a proof of the
> > amount of work to crack a cipher or termination/non-termination
> > of some process.) In particular I don't yet understand
> > your first sentence.
>
> Then you'd have no idea whether "the above constitutes a
> proof" or not would you?
>
> The nice thing about the previous solution is that it doesn't
> require as much background. You would have found that it
> efficiently recovers the secret if you'd bothered to try.
> "Rank" will probably be a few chapters into an introductory
> linear algebra text.
I was not explicit and did not say that what you wrote seems
not to be concrete enough. You wrote [If AS is n by n with
rank m < n, then you can express AS as an n by m times an
m by n]. So AS is to be expressed as CD where C is n*m and
D is m*n. Which method given in the common textbooks of
linear algebra are you referring to? Are C and D unique or
could I take any candidates? I need some concrete
instructions from you, for I like very much to see if I
could actaully carry out the computation of a tiny example,
for that would obviate the need of any further discussions.
Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Nonlinearity question
Date: Tue, 19 Dec 2000 11:25:46 +0100
Benjamin Goldberg wrote:
>
> True enough... but how do I verify the quality of a 128x128
> substitution?
There have been written software packages to study that.
As far as I am aware, the time needed increases quite rapidly
with the size of the S-boxes. I don't know the real amount
but I guess that the time for a 128-bit S-box is huge.
M. K. Shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Result of an old thread?
Date: Tue, 19 Dec 2000 10:27:43 GMT
Jakob Jonsson wrote:
>
> "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in the message
> news:[EMAIL PROTECTED]...
> >
> >
> > Jakob Jonsson wrote:
> > >
> > > The scheme is insecure because there is only one solution S:
>
> Sorry, I meant that the scheme is insecure because the solution is
> easy to find. There is only one solution since there is no shared
> secret.
>
> > > Put
> > >
> > > X = AS,
> > > Y = SB,
> > > Z = ASB.
> > >
> > > To determine S, find any nonsingular W such that
> > >
> > > X*W = Z (i.e., ASW = ASB).
> > >
> > > [This is an equation system with n^2 equations and n^2 variables
> > > (all elements in W), but the equations are dependent since X is
> > > singular, so we will have many solutions.]
> >
> > Sorry for my ignorance. How do you 'algorithmically'
> > determine a nonsinglular W? (Or do you have to depend on
> > your luck?) Since X is singular, the Gaussian elimination
> > process operating on X will get stuck before reaching the
> > last row, if I don't err.
>
> All solutions can be found efficiently via Gaussian elimination in the
> usual manner. We won't get stuck. Instead we will get a bunch of zero
> rows in the matrix X, and since there are solutions to the equation
> X*W = Z, the corresponding rows in Z will be zero as well. Just drop
> these rows and solve the remaining system. You will obtain some
> parameters (one parameter in each column of W for each zero row in X
> after Gaussian elimination) in your solution. For example, with two
> zero rows in a 4x4 matrix system, the solution in one column of W will
> be something like
>
> w_1 = a s + b t + c
> w_2 = d s + e t + f
> w_3 = s
> w_4 = t,
>
> where s and t are parameters and a,b,c,d,e,f are known constants. Any
> values on s and t will give a solution.
But does this allow you to find the original matrix S?
Especially considering that if the implementor is smart, he'll choose it
in some way OTHER than simply putting in an all zeros row or column.
It's relatively easy to find singular matrices that have all elements
nonzero, all it takes is a careful choice of values along the diagonal.
> To find a nonsingular matrix you will have to guess, but in GF(q) the
> probability that a random nxn matrix is nonsingular is quite high, at
> least 0.28 for q=2, higher for larger q, and close to 1 for very large
> q (*), so if you simply choose parameters at random, you will find a
> nonsingular matrix pretty soon.
Hmm, does this work for GF(2^N) as well as GF(p) ?
> Jakob
>
> (*) The number of nonsingular nxn matrices in GF(q) is
> (q^n-1)*(q^n-q)*(q^n-q^2)*...*(q^n-q^{n-1}). To get the fraction P of
> nonsingular matrices, divide each factor with q^n and compute the log
> of the result. You obtain
>
> log(P) = log(1-1/q) + log(1-1/q^2) + log(1-1/q^3) + ...
>
> Now approximate.
BWT this forumula indicates that for q=2, P=0.288788095 for 30 terms.
Rounding to 2 significant digits results in P=.29 (where earlier you
said .28)
--
There are three methods for writing code in which no bug can be found:
1) Make the code so straightforward that there are obviously no bugs.
2) Make the code so complicated that there are no obvious bugs.
3) Insist that any apparent bugs were really intentional features.
------------------------------
** 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
******************************
