Cryptography-Digest Digest #290, Volume #13 Fri, 8 Dec 00 01:13:00 EST
Contents:
Re: breaking rsa knowing the original text (Bryan Olson)
Re: wrapper code (Rex Stewart)
Re: Idea for ciphering? (Bryan Olson)
Re: Modular arithmetic ("KENNETH H MARTIN")
Re: Hamming Distance (John Myre)
Re: wrapper code (Rex Stewart)
Re: keysize for equivalent security for symmetric and asymmetrickeys ("Paul Pires")
Re: keysize for equivalent security for symmetric and asymmetric keys ("Paul Pires")
Re: Hamming Distance ("Jlowrie")
Re: Hamming Distance ([EMAIL PROTECTED])
Re: How to embed a key in executable code? ("Matt Timmermans")
Something wrong with LockNut asym cypher ("Dugg")
Re: Something wrong with LockNut asym cypher ("Pete Schnier")
Re: Something wrong with LockNut asym cypher ("Kewl")
Re: Encrypting messages in images?? (Cassj)
Re: Modular arithmetic (John Savard)
Re: Hamming Distance (David Hopwood)
Re: NT 4.0 and MD4 Hash (David Hopwood)
Re: Revised cipher (Benjamin Goldberg)
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: breaking rsa knowing the original text
Date: Thu, 07 Dec 2000 23:00:51 GMT
[EMAIL PROTECTED] wrote:
> Hi, I'm trying to figure out if it is much simpler to
> break RSA knowing the original text and the encrypted text.
> I mean, if some knows the original and the encrypted data
> how easy will be to get the key ??
Giving an attacker ciphertext with corresponding
plaintext will not help him recover the RSA key. It's
a public key cipher so he can create all the plaintext/
ciphertext pairs he wants.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: wrapper code
Date: Thu, 07 Dec 2000 23:06:38 GMT
In article <90mh9b$l54$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Steve Blinkhorn) wrote:
> Rex Stewart ([EMAIL PROTECTED]) wrote:
<<snip>>
>
> Somewhere in between the two, actually: I can easily do the cast, and
> for the application I have in mind ECB is probably fine. What I was
> looking for is standard practice for encoding strings that are not
> multiples of eight bytes long, for instance - should I just null pad
> at the end, or does this make some methods vulnerable? I imagine the
> issue is *amazingly* mundane, but the FAQ doesn't offer anything.
> It's all very well, for instance, to describe something like blowfish
> as a drop-in replacement for DES: what I would like to see is some
> straightforward code to drop it into...
>
> --
> Steve Blinkhorn <[EMAIL PROTECTED]>
>
Well, it might be considered mundane - but not amazingly
mundane. There is a standard for padding, but it gets
debated from time to time. I don't remember the exact
details, but goes something like:
Pad with a 1 bitt and a string of 0's, end with the
total number of bits added, and if your program EVER
pads ALWAYS pad (prevents the ambiguous situation of
ending with 8 and wondering if that is the last byte
of the file, or is that 8 the 8 bits of padding?)
If you do a search of this newsgroup for padding,
you should find the conversations about it, and
I think also the link to the standard. The debate
centers around the fact that padding introduces
known plaintext - a reason for not going with ECB.
If the end of the string one byte longer than a
multiple of 8 bytes, you end with
x?? f0 00 00 00 00 00 40 as the last block
and only the first byte is unknown. Can be
pretty bad in some situations.
BTW, I don't do this full time, so it would be
good to check my referances. And I think this
SHOULD be in the FAQ - but I realize they can only
put so much into a FAQ.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Idea for ciphering?
Date: Thu, 07 Dec 2000 23:13:25 GMT
[EMAIL PROTECTED] wrote:
> Mok-Kong Shen wrote:
> >
> > Sorry, I erred. Since the F's are secret, the STT can be
> > public.
>
> Right =)
So what exactly is the public key and how does one ecrypt with it?
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "KENNETH H MARTIN" <[EMAIL PROTECTED]>
Subject: Re: Modular arithmetic
Date: Thu, 7 Dec 2000 18:33:13 -0500
You are right, Mike. I had the wrong algorithm in my program. And
thanks for correcting my fuzzy number.
Because p=65537 is prime, every number from 1 to p-1 has a unique modular
inverse. For example 1/5 mod 65537 = 26215. Because 5*26215 = 1 mod 65537.
Mike Scott
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Hamming Distance
Date: Thu, 07 Dec 2000 16:34:33 -0700
Matt Timmermans wrote:
<snip>
> HDist(A,B) >= |Pop(A)-Pop(B)|
<snip>
And also HDist(A,B) <= Pop(A) + Pop(B), so we have
bounds on both sides. Of course, as you pointed out,
if Pop(A) and Pop(B) are about 128, you don't learn
anything of consequence.
JM
------------------------------
From: Rex Stewart <[EMAIL PROTECTED]>
Subject: Re: wrapper code
Date: Fri, 08 Dec 2000 00:11:10 GMT
In article <90mh9b$l54$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Steve Blinkhorn) wrote:
> Rex Stewart ([EMAIL PROTECTED]) wrote:
>
> Somewhere in between the two, actually: I can easily do the cast, and
> for the application I have in mind ECB is probably fine. What I was
> looking for is standard practice for encoding strings that are not
> multiples of eight bytes long, for instance - should I just null pad
> at the end, or does this make some methods vulnerable? I imagine the
> issue is *amazingly* mundane, but the FAQ doesn't offer anything.
> It's all very well, for instance, to describe something like blowfish
> as a drop-in replacement for DES: what I would like to see is some
> straightforward code to drop it into...
>
> --
> Steve Blinkhorn <[EMAIL PROTECTED]>
>
I went and looked up the conversations, as I feared a search for
Padding got 320 hits. If you search for "Data Padding For Encryption"
you will find a good conversation. Here is a clip from one of the
messages.
_____________________________
RFC 1423 Mechanism
The following padding mechanism from [w] should be
used with DES- CBC if the data to be encrypted is octet
aligned, unless the security policy dictates otherwise:
The input to the DES CBC encryption process must be padded to a
multiple of 8 octet, in the following manner. Let n be the length in
octets of the input. Pad the input by appending 8-(n mod 8) octet to
the end of the message, each having the value 8-(n mod 8), the number
of octets being added. In hexadecimal, the possible paddings are:
01, 0202, 030303, 04040404, 0505050505, 060606060606,
07070707070707,
and 0808080808080808. All input is padded with 1 to 8 octets to
produce a multiple of 8 octets in length. The padding can be removed
unambiguously after decryption
_________________________________
I don't think the issue was ever completely settled. The main
issue seems to be static padding provides a known plaintext and
random padding could provide a subliminal channel.
--
Rex Stewart
PGP Print 9526288F3D0C292D 783D3AB640C2416A
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetrickeys
Date: Thu, 7 Dec 2000 16:18:27 -0800
Peter Fairbrother <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> in article [EMAIL PROTECTED], Paul Pires at [EMAIL PROTECTED]
> wrote on 4/12/00 8:05 pm:
>
> >
> > lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> >> Bob Silverman writes:
> >>> Fortunately, no one cares what you expect. I suggest you do
> >>> the arithmetic to see exactly how fast a computer would need
> >>> to be to break a 128-bit key in reasonable time.
> >>
> >> Futurist Eric Drexler projects the capabilities of mature nanotechnology
> >> in his book Nanosystems. "[A] 1000 MIPS computer can occupy less than
> >> one cubic micron and consume less than 0.1 microwatt of power" (page 19).
> >> One cubic kilometer of such devices executes 2^120 instructions per
> >> second.
> >
> > Hmmmm. A one cubic meter "computer" contains 10^18th mini's? Burns 10^11th
> > Watts? Might get a little warm.
> > Estimates of computing power growth ALWAYS
> > fail to querry the packaging guy. Maybe a physics buff can tell us if this
is
> > less
> > energy density than that of our sun.
>
> It's a lot but nowhere near the Sun, sorry, it's pretty close to the power
> densities found in inert-gas lasers used for entertainment purposes today
> (actually less than some of them).
Thanks!
I guess I got a little carried away. The point I had was that there are more
physical laws involved in predicting computing power than people like to
think. When making these claims, a sign that a quick check of such things
conservation of energy, momentum and mass. At 100Kw per cubic centimeter,
this thing is going to be a little hard to operate.
Did anyone notice that the reference was citing a computer with a noticable
gravitational feild?
Paul
>
> Peter
>
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: keysize for equivalent security for symmetric and asymmetric keys
Date: Thu, 7 Dec 2000 16:25:03 -0800
John Myre <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Trevor L. Jackson, III" wrote:
> <snip>
> > The human body produces about one watt per pound. The Sun produces less
than
> > this. Since the Sun has a density below unity (it would float) it also
produces
> > less energy per unit volume.
>
> Joke, right?
I think he answered the question I asked, which was not the question
I meant :-) Funny how that works.
If you took total suns output and divided it by unit voulume, his wag is
probably
right. It is a gas bag held out by light pressure. Total output per unit surface
area
and I think Peter Fairbrother got it.
Either way, the previous post was citing a computer with a noticable
gravitational feild. Maybe I'm just old fasion but a prediction adopt
a few common sense constraints.
>
> JM
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Jlowrie" <[EMAIL PROTECTED]>
Subject: Re: Hamming Distance
Date: Fri, 08 Dec 2000 00:56:18 GMT
First are you calculating both hamming(i,j) and hamming(j,i)?
It is hard to tell from the pseudo-code...
There are only n choose 2 distinct distances which is 32640 in your case,
not
n squared (65536). This cuts it by a about 1/2 if you aren't already doing
it.
let me spell in out in code:
for (int i=0; i<list.length; i++)
for (int j=i; j<list.length; j++)
getHamming( list[i], list[j] );
Now are the strings totally different each time you perform this
calculation?
If not, and each are only infrequently changed then you can use caching to
help.
You would skip i,j if both string i and string j were unchanged. If X% are
left unchanged (say 50%), then you
save by a factor of 1/X (2-fold in this case)
Finally, be sure to try the MMX code elsewhere in this post. I clock it at
almost 3 times faster than my
C implementation.
This calculation is quite common in Genetic Algorithms by the way. I'd be
curious to know of
your application?
Jeff Lowrie
<[EMAIL PROTECTED]> wrote in message
news:R4yX5.74817$[EMAIL PROTECTED]...
> Given a list of binary strings (256 bits each) is there an
> time-effecient way to find the set of strings within a certain hamming
> distance from each member? Currently, I'm doing a simple iteration:
>
> foreach i in list:
> remove i from list;
>
> foreach j in list:
> if (hamming(i, j) < x)
> do_something
> next j
> next i
>
> The bottleneck is the hamming() function, which xors the strings, then
> does a software population count on the result. However, it's already
> a reasonably fast procedure, and I'd like to know if there's a way to
> reduce the total number of calls before I try squeesing more speed out
> of it. (The problem is, the number of calls grows pathologically with
> the length of list)
>
> Suggestions and/or pointers to references on methods for either
> reducing the number of calls or speeding up the calculation itself are
> greatly appreciated. For the sake of hamming, you can assume that the
> inputs are always 256 bit binary strings, and the underlying
> architecure is x86. I would prefer to avoid MMX, but I'm curious if it
> could be used to speed things up.
>
> --
> Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Hamming Distance
Date: Fri, 08 Dec 2000 02:16:30 GMT
Matt Timmermans <[EMAIL PROTECTED]> wrote:
> HDist(A,B) >= |Pop(A)-Pop(B)|
> This is so simple that it will probably be worth something to sort the list
> by population count. Bear in mind, though, that there are a whole lot more
> 256-bit strings with a population count of around 128 than there are with
> counts near 0 or 256, so you might not get the terriffic improvement you
> expect.
Thanks. I got a 5.5 fold increase in the population count today, so I
tend to regard the algorithm question as mostly closed. With a couple
more profiling iterations and minor changes, I expect it to drop off
as the overwhelming hot spot.
In fact, with the improved population count and some reworking of the
input, I can probably get the sort for next to free. The resulting
time savings will probably drop it down below a bunch of hot spots in
someone else's module, which is of course, the end goal performance
tuning. ;)
--
Matt Gauthier <[EMAIL PROTECTED]>
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: How to embed a key in executable code?
Date: Fri, 08 Dec 2000 02:21:35 GMT
You missed the important part. To prevent copies, the signature must tie
the software to a CPUID, ethernet address, or something like that. In the
absence of all of these, you have to tie the software to a plaintext license
file that has the user's name and address in it and clearly visible, or make
it put that information up in a splash screen when it starts. Having their
name and address in the file is enough to dissuade a would-be pirate from
distributing illegal copies.
This can only be practically defeated by reverse engineering, so the
question is: "Is reverse engineering always possible"?
There is certainly no known polynomial-time algorithm for reverse
engineering, so why do we always assume that reverse engineering is feasible
in practice? (More specific -- this program performs DES encryption with a
built-in key. Write a program that can extract that key in polynomial time)
Ok... it has been demonstrated time and again, but that doesn't mean that
susceptibility to reverse engineering is an intrinsic property of programs.
It's more likely that it's simply an emergent property of the software the
people tend to write -- our code follows our patterns of thought, and our
patterns of thought are similar to the thought patterns of others, which
tends to make our code comprehensible to others.
------------------------------
From: "Dugg" <[EMAIL PROTECTED]>
Subject: Something wrong with LockNut asym cypher
Date: Fri, 8 Dec 2000 04:36:02 +0200
Reply-To: "Dugg" <[EMAIL PROTECTED]>
I think there something wrong with the asymmetrical cypher in this package.
It do not change sometimes even with a different key.
Am I doing something wrong?
If you use this package please email me.
I desperate
[EMAIL PROTECTED]
------------------------------
From: "Pete Schnier" <[EMAIL PROTECTED]>
Subject: Re: Something wrong with LockNut asym cypher
Date: Fri, 8 Dec 2000 09:10:17 +0200
Reply-To: "Pete Schnier" <[EMAIL PROTECTED]>
You must be doing something wrong.
Its a salted function so the cipher changes every time.
Dr Pete Schnier
Dugg <[EMAIL PROTECTED]> wrote in message
news:90phq1$kn$[EMAIL PROTECTED]...
> I think there something wrong with the asymmetrical cypher in this
package.
> It do not change sometimes even with a different key.
>
> Am I doing something wrong?
> If you use this package please email me.
> I desperate
>
> [EMAIL PROTECTED]
>
>
------------------------------
From: "Kewl" <[EMAIL PROTECTED]>
Subject: Re: Something wrong with LockNut asym cypher
Date: Fri, 8 Dec 2000 17:22:22 +0200
Reply-To: "Kewl" <[EMAIL PROTECTED]>
There was a version released where they forgot to set a compilation flag.
That flag stops the padding from working in the RSA algorithm for debugging
purposes.
It still kind of worked.
The version at http://www4.50megs.com/johnnyco/ works properly.
Dugg <[EMAIL PROTECTED]> wrote in message
news:90phq1$kn$[EMAIL PROTECTED]...
> I think there something wrong with the asymmetrical cypher in this
package.
> It do not change sometimes even with a different key.
>
> Am I doing something wrong?
> If you use this package please email me.
> I desperate
>
> [EMAIL PROTECTED]
>
>
------------------------------
From: Cassj <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,alt.2600.hacker,alt.security
Subject: Re: Encrypting messages in images??
Date: Fri, 08 Dec 2000 04:17:08 GMT
Thanks for the heads up. I didn't know about the crack.
Cheers....Cass
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Modular arithmetic
Date: Fri, 08 Dec 2000 04:18:03 GMT
On Thu, 7 Dec 2000 16:01:27 -0500, "KENNETH H MARTIN"
<[EMAIL PROTECTED]> wrote, in part:
>Please forgive my ignorance, but to decrypt an IDEA cipher
>I need to find the multiplicative inverse of a 16-bit number,
>Mod 66537. What if there are no inverses less than the
>modulus, say for a relatively prime number like 5? Is there
>a trick to this?
Well, 65537 is a prime number, so you won't have that problem.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Fri, 08 Dec 2000 05:26:21 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hamming Distance
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
> Given a list of binary strings (256 bits each) is there an
> time-efficient way to find the set of strings within a certain hamming
> distance from each member? Currently, I'm doing a simple iteration:
>
> foreach i in list:
> remove i from list;
>
> foreach j in list:
> if (hamming(i, j) < x)
> do_something
> next j
> next i
1. Split the list into 257 sublists according to the Hamming weight of
each string. Since
|weight(i) - weight(j)| <= hamming(i, j) and
|weight(i) - weight(j)| = hamming(i, j) (mod 2),
j only needs to be searched for in x+1 of the sublists.
2. Let m be a word size with 2x < m < 256, and let xorhash(s) be the
xor of the words of s. Precalculate xorhash(s) for each string.
Then hamming(xorhash(i), xorhash(j)) = weight(xorhash(i xor j)) <=
hamming(i, j), so
hamming(xorhash(i), xorhash(j)) <= x
can be used as a quick test to eliminate pairs of strings that
are definitely not within Hamming distance x. (I.e. most of the
population counts only need to be done on a single m-bit word.)
These optimisations don't change the asymptotic complexity, which is
still O(n^2), but they should improve the practical performance when
x is small.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOjBggjkCAxeYt5gVAQGGkwgAkvWQrp8e+EmXGGl2cayvT/okLh4+5pam
ziNHswFNYwjoPNDDmc66GMDL4sgSFMLkvU58yXybxBy4Uuwx34L+Np+ESiuJHkiU
TCvcUa0/G5tk43e1UDb4RO5d57jCv/l89BuVsuRh0b/NBPRjnFXtIZPDp6Ulr/mB
DfSSFBsLEZy7Z1ySDXrsq78aFx1Oi5RBYihcStIKHA6aDdZeeSYGpHl08YK+uJ3K
NWT2RuSeSF1GGRdvYckPueULlwvGykaXRMuM7BF/8XiDk34Z/yBFGB0KOg/Yip/Q
dH8J8Rs0A54lQlF6GmddG3bcaya0x+1koGDk+p/Giu+/3JxoYz9QlQ==
=pCm3
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 08 Dec 2000 05:38:34 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: NT 4.0 and MD4 Hash
=====BEGIN PGP SIGNED MESSAGE=====
I wrote:
> [EMAIL PROTECTED] wrote:
> > Please fix the error in my ways.. ;-)
> >
> > I was under the impression that the NT hash (not the LM hash) was a
> > straight MD4 hash with no salt value.
>
> It is, but of a Unicode (big-endian UCS-2 encoded) string.
Correction: it is little-endian UCS-2 encoded. See RFC 2433.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOjBznTkCAxeYt5gVAQHAIggAmOUc551aoCYkzz4aqvkTWyMIlKFA6GmQ
VYwM/53FuT8DGQpeQeeJT3aThfnhLFL/LcINsEUU17L69DIWvzi2ql1f/HfqhS49
8kE0eP21GTQoeRtLq3bqNIlp+YWd+51YOMrZqcJBzWneEh/n51Ft412qEh2aJWEw
rRWnsq04unnI3SV/sFumnVCa+8GvmcPqDMYTxtoUO0Z9FsSRRdsi62NcoBAbTv4Q
uNawjU3OHOJGmmuQl1PVTstCjuQ1O/7wkxjvbto0qu40ozKYajaHdCEyxl28vveX
pDAfhiATQKU8z3W1w9BRu3bO9H41YQ32RbbB3+xWNWcgI53cbySNWQ==
=pK0c
=====END PGP SIGNATURE=====
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Revised cipher
Date: Fri, 08 Dec 2000 05:43:27 GMT
Jorgen Hedlund wrote:
>
> Benjamin Goldberg wrote:
> >
>
> Thanx for your response...
>
> (and I know this isn't any programmers group, but the readers
> might need this anyway.. =)
>
> > Jorgen Hedlund wrote:
> > >
> > > >Benjamin Goldberg wrote:
> > >
> > > <snip alot>
> > >
> > > <snip some more>
>
> <snip>
>
> > Umm, oops? Hey, at least it's better than xyz's!
>
> Censored the name, no need to pick on anyone publicly =)
Don't worry, lots of people agree that D.A.S. writes shitty looking,
unreadable code. Only one person is going to call Mr. Scott's code
"good", and that's the author himself.
> > I'll add some space and comments.
> >
> > > Some guidelines to get better comments on your code
> > > - please add some 'air' into the code. It's suffocating =)
> > > - use understandable naming conventions on your variables
> > > - and for G..'s sake, use braces whenever you open a block of
> > > code.
> > >
> > > ...and ofcourse, a little more comments _in_ the code would
> > > be great..
> >
> > Ok, will do. Umm, where don't I use braces around blocks of code?
>
> Use common sense =) Like these examples.
>
> around if statements
>
> if (abc)
> {
> ...
> }
> else
> {
> ...
> }
I tend to do:
if( abc ) {
...
} else {
...
}
The braces are there, but placed differently. It's a matter of
preference. Both are perfectly valid styles; the important things for
legibility are that one does place the braces consistently, and that one
indents consistently. And as to you comment about using common sense,
what I *meant* when I said "where don't I," was "where haven't I."
> loops of any kind
>
> for (init; condition; uhm)
> {
> ...
> }
>
> The general rule is to always use braces around code that might
> or might not run, or might run more than once...
> to simply enhance readability...
>
> etc...
The braces are there; it's the extra new lines that you're looking for
and don't see.
> > > > void gb_init() {
> > > > static int initialized = 0;
> >
> > Well, I'm sure you can guess what the above thing is for. It's so
> > that the body of this function never is called more than once.
> > Since this [and it's use] should be obvious, I won't mention it
> > again.
>
> doh! =)
>
> > > > const int polys[8] = {
> > > > 0xfdbf, 0xf7ef, 0xeff7, 0xdfef, 0xd7ff, 0xb7ff,
> > > > 0xfff6, 0xfff5 };
> >
> > These are 8 order-16 primitive polynomials with coefficients in
> > GF(2). Each one of them defines a finite field in GF(2**16). Since
> > they are primitive, not just irreducible, 2**x is a generator in
> > each of these fields. The linear step of the encryption is
> > multiplication of the 8 rows by 2**32, with each row being in one of
> > these 8 fields.
>
> GF?
>
> And ** means power of, right? Like 2**2 equals 4? (I'm used to 2^2,
> but that isn't really a good thing to use in the code since I believe
> that means OR:ing or something.. =)
GF means Galois Field. GF(2**16) means that the elements of the field
are polynomials of the form a_0*x**15 + a_1*x**14 ... a_15, where each
coefficient, a_i is an element from GF(2).
Addition and multiplication of numbers in GF(p) (where p is a positive
integer, and usually prime), is done in the normal way, followed by
doing modulo p. Elements of the field GF(p) are 0..p-1.
Additions and multiplications in GF(p**n) are first done as normal
polynomial additions or multiplications (but with the coefficients in
GF(p)), and then are reduced modulo some special polynomial, which is
the characteristic of the field (I think this is the right term), which
is an order-n polynomial with coefficients in GF(p). Order-n means that
the highest exponent of the modulo is n. Usually, GF(p**n) is actually
GF(2**n), as these values can easily be represented as binary numbers.
Elements of GF(2*n) are polynomials of up to n terms, with a maximum
order of n-1, and can be represented efficiently as an n bit binary
number.
> > > > uint8 pow[256], log[256];
> >
> > These are power and logarithm tables for the function 3**x in
> > GF(2**8).
>
> Ah, tables to enhance performance?
>
> > > > int i, j, k;
> > > > if( initialized ) return;
> > > > for( i = 0; i < 8; ++i ) {
> > > > int poly = polys[i], j;
> > > > for( j = 0; j < 16; ++j )
> > > > mask[15-j] |= ((poly>>j)&1) << i;
> > > > }
> >
> > The above takes the 8 16-bit-polys and turns them sideways :)
>
> You're AND:ing with 1, that will clear everything but the LSB, why?
Essentially, I take 8 integers with 16 bits each, and create 16 integers
of 8 bits each. Each of the 16 bit integers defines the characteristic
of one Galois Field of type 2**16. Each of the produced 8 bit integers
defines 1/16th of 8 different GF(2**16) fields.
> > This allows the 8 encryption multiplications by 2**32 to be
> > calculated in parallel.
>
> *tilt*
Actually, consider that when I said "2", I meant the polynomial "x"
(with a 1 coefficient for x, and all other coefficients 0).
To multiply by x means that you add one to all the coefficients of the
polynomial; In the represented form, this means multiplying the integer
by two, or shifting left by one. The linear step thus is multiplying
each of 8 rows by the polynomial "x**32", and then reducing modulo that
row's Galois Field characteristic.
> > > > for( i = 0, j = 1; i < 256; ++i ) {
> > > > log[pow[i] = j] = i;
> > > > j ^= (j << 1) ^ ((j & 0x80) ? 0x1b : 0);
> > > > }
> >
> > Hmm, that should be 0x11b, not 0x1b. Whoops!
>
> =)
>
> > Compute 3**x in GF(2^8). pow[x] = 3**x, and log[3**x] = x.
> > 3**x is a generator function in this field.
> > This is needed for the calculation below.
>
> <snip>
>
> > Yes, this is indeed very ugly. This loops creates the same sbox as
> > Rijndael (and it's inverse). How is it doing this? Umm, err, I
> > dunno. Maybe read the Rijndael paper? I got this stuff out of
> > somebody else's AES implementation, and simplified it (it was even
> > uglier before!).
>
> It seems I need to study Rijndael, since I don't even know what a sbox
> is. Any good papers around? Or perhaps even some source code that's
> heavily commented? =)
You don't know what an sbox is! Ack. It's a substitution box.
Stick an integer in one side and another comes out the other; it's
usually implemented as a table (array) lookup.
It's a common thing to have in all sorts of ciphers. If you're
interested in this cipher, you don't need to study Rijndael except
perhaps to learn why that particular sbox is good. (This doesn't mean
you can't decide to study it simply for the sake of studing it, but let
me warn you, some parts of Rijndael are complicated and confusing,
especially for a beginner.)
There's a number of books you can read about cryptography, and there are
references to them on this newsgroup. People ask which books to read
all the time, see those messages (I don't recall all the suggested
titles offhand).
> > > > initialized = 1;
> > > > }
> > >
> > > <snip rest of the code>
>
> BR/jh
>
> --
> ------------------------------------------
> Jörgen Hedlund, Software Engineer
> Ericsson Software Technology, BGw
> ------------------------------------------
--
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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
