Cryptography-Digest Digest #570, Volume #9 Thu, 20 May 99 11:13:02 EDT
Contents:
Re: Encryption starting ([EMAIL PROTECTED])
Re: prime numbers and the multplicative inverse ([EMAIL PROTECTED])
Re: Can Somebody Verify My DES execution? (Hagen Ploog)
RC4 based hash ([EMAIL PROTECTED])
Re: where can i find a frequency list? (Patrick Juola)
Re: Complexity Question (Patrick Juola)
Re: CRC16 polynomials (Russell Harper)
Re: Reasons for controlling encryption (Mark E Drummond)
Re: PK Security (Mark E Drummond)
Symmantic question (Mark E Drummond)
Re: Complexity Question (Bob Silverman)
Re: prime numbers and the multplicative inverse (Emmanuel BRESSON)
Looking for pointers (Mark E Drummond)
Re: prime numbers and the multplicative inverse (Bob Silverman)
Re: Complexity Question (Emmanuel BRESSON)
Re: Symmantic question (Kent Briggs)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Encryption starting
Date: Thu, 20 May 1999 11:19:14 GMT
> Yes, read the group, but don't post "better" algorithms that you think
> that you just invented.
Hmm... Really... Oooh you are so mature and respectful of others. I
appreciate your sincere response and look forward to future flames with
your tasteful name.
> Applied Cryptography is indeed an excellent book, but as the name
> suggests, it is intended mostly for people who want to implement a
> specific protocol or algorithm. It lacks the mathematical rigor of say
> _Cryptography: Theory and Practice_ or _The Handbook of Applied
> Cryptography_, although it is very useful as a reference book, say
when
> you forget how to do a blind signature scheme.
Well it's a good book, and actually does cover the basics. Have you
actually read the book? Hm... first page ('What is ciphertext') seems
like an algorithm description to me :)
> The easy to read papers are nearly as helpful as the more difficult to
> read ones. You might get an intuitive sense of the design elements
that
> make an algorithm "good" (ex. large S-boxes) but you won't gain any
> more understanding of why these elements make an algorithm secure.
>
These 'easy' read papers will describe simple algorithm, and their
background. It's a good way to see what real algorithms are like.
Like RC5 for example is 3 lines long, not very complicated. You can
also find the cryptanalysis of it to find out why it's strong for
example.
You don't start in cryptography without reading other papers. I made
that mistake :(
> You will most probably *not* see whether your ideas are good or bad.
> Rather, you will think that it is great, post it to the world, annoy
> many people, and someone will find a problem with it.
How do you think RSA, DH and others started? Are you really that
dense? You can read all the books, papers and lectures you want, but
if you don't actually play with ideas (new or old) and see how they
actually work, you will never learn anything.
> I think you need to clarify your understanding of the relationships
> among fields, groups, and rings. You can't use the terms without
regard
> for their definition...
I got those mixed up. That's because the reply to my msg was rather
oblivious to fields<->groups. I will just read the paper on IDEA and
see which it was suppose to be.
Hey Mr. LordCow (that's a wierd name btw), why not pull your head from
your $#!, and be a little more constructive.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: prime numbers and the multplicative inverse
Date: Thu, 20 May 1999 11:07:26 GMT
> NO! The field does NOT need to be a prime field. GF(2^101) for
> example, is not a prime field. Yet it is indeed a field, so every
> non-zero element has an inverse.
That's wrong, because if your modulus can satisfy gcd(p, a) > 1 (a is
any number in from 1 to p-1) then some numbers will not have inverses.
> I hope not, because your answer (to the question as asked) is WRONG.
I have seen the page. his information is not only correct it is
presented professionally too :)
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Thu, 20 May 1999 14:10:01 +0200
From: Hagen Ploog <[EMAIL PROTECTED]>
Subject: Re: Can Somebody Verify My DES execution?
Zulkifli Hamzah wrote:
> Hi Forum,
>
> I'm newbie to encryption software development (and newbie to this
> group either) but ...
>
> I've made a simple program implementing stadard DES as described in
> Cryptography and Network Security by William Stallings, using exactly
> same tables and s-boxes.
>
> Here some output of my program (spaced manually for readability), using
> the same key input with 3 plaintext inputs each differ by 1 bit. (The book
> gives some output reference for SDES, but not much on DES).
>
> If anybody outthere has coded the DES algorithm and verified to work
> successfully,
> could you help verifying mine? - Thank you in advance.
>
> ZulH.
>
> Key:
> 0000001 1001011 0100100 1100010 0011100 0011000 0011100 0110010
> -------------------
> PlainText:
> 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
> Output:
> 10101011 11010000 10101110 01100111 11111010 10111101 10101010 10000010
> -------------------
> PlainText:
> 10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
> Output:
> 11111111 11110101 11101111 11011111 11110101 10111111 01010101 01010110
> -------------------
> PlainText:
> 01000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000
> Output:
> 01000011 11011111 00111100 01100111 11111010 11111101 10101010 10111111
> -------------------
Hi,
how about selfvalidating, keys are available at:
gopher://wiretap.spies.com:70/00/Library/Article/Crypto/vectors.des
Regards,
Hagen
------------------------------
From: [EMAIL PROTECTED]
Subject: RC4 based hash
Date: Thu, 20 May 1999 11:25:21 GMT
Just wondering,
If you used the RC4 key schedule as a compression function (using the
message as the key), then the RC4 RNG as the actual hash output
wouldn't that a neat basis?
Some things though, such as messages longer then the key schedule,
possibly repeat the key schedule? There are only 2^1684 possible
combinations of the deck however, Would a restriction have to be
imposed?
Another idea is to statistically (entropy) encode all messages, so an
attacker would have less control on the actual key values in the key
schedule.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: where can i find a frequency list?
Date: 20 May 1999 08:43:50 -0400
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>
>>
>> Easy enough to roll your own.
>
>To write a program is trivial. But to get the material (and the
>resources) is another matter.
Not any more. There's this great big World Wide Web out there
with all the text you could possibly want. I suggest you stop
by project Gutenberg (q.v.).
>> And, I suspect, not the stuff that you would find published tables
>> for (or find them to be any use if someone *were* fool enough to
>> publish such a table).
>>
>> In general (and vastly oversimplified), most of the "high frequency"
>> stuff in linguistic distributions is general, language-specific but
>> not document-specific information. For example, the most common words
>> in almost any English document of interest are words like 'the' and 'of';
>> high-frequency, low-meaning "function words."
>>
>> When you subtract out the high frequency digraphs, you'll be left with
>> the underlying distribution of the low(er) frequency words in the
>> document of interest, which tend to be very strongly associated with
>> the content and register of the document. So the words that are moderately
>> common in (e.g.) a Ph.D. dissertation will have little to do with the
>> words that are moderately common in an issue of _Sports Illustrated_;
>> furthermore, the January _Sports Illustrated_ may well have little to
>> do with the July _SI_ as the content will have changed so radically.
>>
>> This *might* be an interesting way to do document classification -- but
>> the cryptographic applications are limited.
>
>I am interested to know by how much the frequency distribution
>of single characters changes through the subtraction for exactly
>the same source materials from which the published tables were
>obtained.
Again, I suggest rolling your own.
-kitten
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Complexity Question
Date: 20 May 1999 08:41:29 -0400
In article <7i07op$1t7$[EMAIL PROTECTED]>,
Mike Murray <[EMAIL PROTECTED]> wrote:
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>
> I was talking to a professor of mine, recently, and she gave me
>some hints on big-O notation, and computational complexity, for a
>problem I've been working on. However, I have one more question
>(which is pretty simple, and I'm relatively sure of the answer), which
>I want to double check.
>
> For a given algorithm, O(n) is in terms of the size of a variable
>n. How do we define the size of n? Is it the actual integer value of
>n, or is it the size of n in terms of length in bits? (which would
>actually be log(base 2) of n). For example:
Depends on the problem at hand.
For example, in the case of the Travelling Salesman Problem, N is
usually defined as the number of nodes in the graph to be traversed.
In the case of factoring, N is defined to be the length of the
number to be factored (in bits or in digits, as you prefer).
-kitten
------------------------------
From: Russell Harper <[EMAIL PROTECTED]>
Subject: Re: CRC16 polynomials
Date: Thu, 20 May 1999 12:58:48 GMT
Thanks! Besides some concrete examples, the paper has a lot of useful
information. It looks familiar, I probably have it filed away somewhere...
/Russell
hapticz wrote:
> ftp://www.internode.net.au/clients/rocksoft/papers/crc_v3.txt
------------------------------
From: Mark E Drummond <[EMAIL PROTECTED]>
Subject: Re: Reasons for controlling encryption
Date: Thu, 20 May 1999 09:02:36 -0400
Doug Stell wrote:
>
> Keep the good stuff out of the hands of terrorist organizations for
> national security reasons.
>
> Keep the good stuff out of the hands of organized crime for law
> enforcement reasons.
These are interesting because my superiors were discussing the idea of
deploying enterprise wide user-to-user encryption using certificates and
one argument _against_ it was that it would let the "bad guys" _inside_
the organisation traffic inappropriate material. eg encrypting
classified material or pictures of your neighbors daughter sans
vetements and emailing it to your friend in <pick you enemy's country>.
To me this is along the same lines as "security through obscurity" and
it is about as dense as you can get.
--
_________________________________________________________________
Mark E Drummond Royal Military College of Canada
[EMAIL PROTECTED] Computing Services
Linux Uber Alles perl || die
...there are two types of command interfaces in the world of
computing: good interfaces and user interfaces.
- Dan Bernstein, Author of qmail
------------------------------
From: Mark E Drummond <[EMAIL PROTECTED]>
Subject: Re: PK Security
Date: Thu, 20 May 1999 09:09:15 -0400
Sundial Services wrote:
>
> Mark E Drummond wrote:
> >
> > Realising that this has much to do with key-length and the algorithms
> > used, in a general sense, how secure is public key cryptography today?
> > iow, how secure is a message that has been encrypted using my Verisign
> > certificate (1024 bit key)?
>
> I can't call myself anyone's expert, Mark, but the phrase that comes to
> my mind is, "secure against what?" If your attacker is the NSA or MI5,
Secure against the general public. We don't have anything that NSA or
MI5 might be interested in on our network. Maybe some of our profs
research might be of interest if other profs out there are in to
stealing that stuff but that is about the extent of it.
--
_________________________________________________________________
Mark E Drummond Royal Military College of Canada
[EMAIL PROTECTED] Computing Services
Linux Uber Alles perl || die
...there are two types of command interfaces in the world of
computing: good interfaces and user interfaces.
- Dan Bernstein, Author of qmail
------------------------------
From: Mark E Drummond <[EMAIL PROTECTED]>
Subject: Symmantic question
Date: Thu, 20 May 1999 10:10:21 -0400
Is there a proper way to complete the following sentances? :
Every bit added to the key length increases the difficulty of an
exhaustive keysearch attack by [?].
Doubling the key length increases the difficulty of an exhaustive
keysearch attack by [?].
Just wondering, even though I may be pretty green WRT crypto I'd at
least like to _look_ like I know what I am talking about ... ;-)
--
_________________________________________________________________
Mark E Drummond Royal Military College of Canada
[EMAIL PROTECTED] Computing Services
Linux Uber Alles perl || die
...there are two types of command interfaces in the world of
computing: good interfaces and user interfaces.
- Dan Bernstein, Author of qmail
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Complexity Question
Date: Thu, 20 May 1999 14:26:01 GMT
In article <7i07op$1t7$[EMAIL PROTECTED]>,
"Mike Murray" <[EMAIL PROTECTED]> wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
>
> I was talking to a professor of mine, recently, and she gave me
> some hints on big-O notation, and computational complexity, for a
> problem I've been working on. However, I have one more question
> (which is pretty simple, and I'm relatively sure of the answer), which
> I want to double check.
>
> For a given algorithm, O(n) is in terms of the size of a variable
> n. How do we define the size of n? Is it the actual integer value of
> n, or is it the size of n in terms of length in bits?
It is the amount of space needed to write down the problem instance.
Whether the size of n is its value or its length in bits depends on the
definition of n itself.
For example, with FFT's the time to multiply 2 n-bit numbers is
O(n log n loglog n). But the time to (say) square k is
O(log k loglog k logloglog k) because now k represents the number
itself and not its size.
> if n = 32,000, would the O(n) be in terms of 32,000, or 16 (bits)?
It depends on what n represents.
> This question is kind of strange, I suppose, but, if we double the
> size of n = 32,000, we have n = 64,000.
No. Here you are talking about n as if it were just an integer, i.e.
a unitless constant. You have not doubled the size of n, but rather
doubled its VALUE. If we double the size of n, we get 3200000000
(i.e. 10 digits instead of 5). Size means the amount of space needed
to represent the number.
> I'm relatively sure that O(n) is in terms of n itself, rather than
> log n, but I want to double check this before I go any farther.
It depends on how n is defined. Another example. If one uses
classical arithmetic and not FFT's then the time needed to multiply
two numbers mod p is O((log p)^2). But the time needed to multiply
two integers modulo a p-bit integer is O(p^2). p is defined
differently in the two specifications.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Thu, 20 May 1999 10:28:04 -0400
From: Emmanuel BRESSON <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: prime numbers and the multplicative inverse
[EMAIL PROTECTED] wrote:
> > NO! The field does NOT need to be a prime field. GF(2^101) for
> > example, is not a prime field. Yet it is indeed a field, so every
> > non-zero element has an inverse.
>
> That's wrong, because if your modulus can satisfy gcd(p, a) > 1 (a is
> any number in from 1 to p-1) then some numbers will not have inverses.
GF(2^101) is a field, then every element has an inverse, whereas Z/2^101,
which is maybe what you are thinking about, is not a field but a ring,
since you have GCD(2^101, 2)=2.
------------------------------
From: Mark E Drummond <[EMAIL PROTECTED]>
Subject: Looking for pointers
Date: Thu, 20 May 1999 09:13:37 -0400
I've studied encryption for the POV of a user and adminstrator and have
a good grasp of the theory behind these systems. Now I would like to
dive a little deeper by studying the mathematical underpinnings of these
systems. However, my math skills are lacking and it has been a while
since I cracked (no pun intended) open a math text. Can someone gives me
some pointers, URLs, appropriate books, what areas of mathematics I
should look at, etc?
--
_________________________________________________________________
Mark E Drummond Royal Military College of Canada
[EMAIL PROTECTED] Computing Services
Linux Uber Alles perl || die
...there are two types of command interfaces in the world of
computing: good interfaces and user interfaces.
- Dan Bernstein, Author of qmail
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: prime numbers and the multplicative inverse
Date: Thu, 20 May 1999 14:32:52 GMT
In article <7i0qde$n8e$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
>
>
> > NO! The field does NOT need to be a prime field. GF(2^101) for
> > example, is not a prime field. Yet it is indeed a field, so every
> > non-zero element has an inverse.
>
> That's wrong, because if your modulus can satisfy gcd(p, a) > 1 (a is
> any number in from 1 to p-1) then some numbers will not have inverses.
>
Your answer shows that you do not understand what a finite field is.
Nor the distinction between a field of characteristic 0, a prime field,
and a non-prime (i.e. extension) field.
May I suggest you read the following:
Lidl & Niederreiter
Finite Fields
Addison Wesley
> > I hope not, because your answer (to the question as asked) is
WRONG.
>
> I have seen the page. his information is not only correct it is
> presented professionally too :)
Did you contradict your professors too?
When an expert in finite field arithmetic tells you something is
wrong, I suggest you listen to him.
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
Date: Thu, 20 May 1999 10:50:03 -0400
From: Emmanuel BRESSON <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Complexity Question
Hi Patrick,
> > For a given algorithm, O(n) is in terms of the size of a variable
> >n. How do we define the size of n? Is it the actual integer value of
> >n, or is it the size of n in terms of length in bits? (which would
> >actually be log(base 2) of n). For example:
> Depends on the problem at hand.
> For example, in the case of the Travelling Salesman Problem, N is
> usually defined as the number of nodes in the graph to be traversed.
> In the case of factoring, N is defined to be the length of the
> number to be factored (in bits or in digits, as you prefer).
To complete:
Formally speaking, O(n) refers to the value of n itself.
On the other hand, could this value be the number of nodes or the length
of a RSA modulus, the point is that n should represent a good complexity
parameter of your system.
A very informal explanation:
n usually represents the size of your input.
Why is n the number of nodes in one case and the number of bits in the
other case?
Well, try to consider the Travelling Salesman Problem with a double number
of nodes => you will need twice much of memory.
==> it is proportionnal
try to consider the Factoring Problem with a double value for the modulus
=> you will need only one more bit and not twice many.
==> it is not proportionnal.
now try to consider Factoring Problem with a double numer o bits => the
memory needed is twice.
==> The good parameter is the length, not N itself
I hope this will be helpful
Bye
Emmanuel Bresson
------------------------------
From: Kent Briggs <[EMAIL PROTECTED]>
Subject: Re: Symmantic question
Date: Thu, 20 May 1999 15:03:38 GMT
Mark E Drummond wrote:
> Is there a proper way to complete the following sentances? :
>
> Every bit added to the key length increases the difficulty of an
> exhaustive keysearch attack by [?].
a factor of 2
> Doubling the key length increases the difficulty of an exhaustive
> keysearch attack by [?].
a factor of 2 raised to the power of the original key length.
--
Kent Briggs, [EMAIL PROTECTED]
Briggs Softworks, http://www.briggsoft.com
------------------------------
** 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
******************************
