Cryptography-Digest Digest #342, Volume #13 Sat, 16 Dec 00 06:13:01 EST
Contents:
Re: Help with code generator/Formula (Simon Best)
Re: files encrypted eight years ago with the unix crypt(1) command. want in
(Alberto65)
How does public key crytography work, mathematically? ("lowtus")
Re: binary vs. text w/ regard to digital signatures (Paul Schlyter)
Re: Visual Basic Source Code (Paul Schlyter)
Re: Visual Basic Source Code (Paul Schlyter)
Re: Visual Basic Source Code (Paul Schlyter)
Nonlinear Diffusion with S-Boxes? (Simon Best)
Re: How does public key crytography work, mathematically? (Benjamin Goldberg)
Re: How does public key crytography work, mathematically? (Simon Best)
----------------------------------------------------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Help with code generator/Formula
Date: Sat, 16 Dec 2000 09:34:29 +0000
Dido Sevilla wrote:
>
> [EMAIL PROTECTED] wrote:
> >
> > Here is my situation. I am trying to figure out a formula/code for a
> > number generator. I have 5000 pairs of the input number and the result.
> > Let me explain. a certain number X is entered into a program. then it
> > returns Y. I have 5000 XY pairs. Can someone lead me to what I need to
> > do to find the formula that creates Y? Is 5000 pairs enough?
>
> If X and Y are 12 bits each, 5000 pairs is enough.
(Only if there's no internal state, otherwise it's a finite state
machine that could have a bigger state than input or output. The term
'number generator' suggests the thing may have an internal state (like a
PRNG), though the rest of the description suggests it's not being used
that way.)
> You can use the
> Quine-McCluskey method for designing digital circuits to find the
> logical equation that produces each bit of Y from all the bits of X, but
> be warned, it isn't efficient (it runs in exponential time!). If you
> can find an efficient (i.e. polynomial time) method, then publish it
> right away and win a million dollars. I believe the problem of finding
> the logical equation corresponding to given inputs and outputs can be
> reduced to the satisfiability problem and hence is NP-complete. There's
> a million-dollar prize out for whoever can prove or disprove that P ==
> NP...
Wow! I didn't realise the Quine-McCluskey method was one of them!
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: [EMAIL PROTECTED] (Alberto65)
Crossposted-To: alt.os.linux.mandrake,comp.os.linux.misc,comp.os.linux.security
Subject: Re: files encrypted eight years ago with the unix crypt(1) command. want in
Date: Sat, 16 Dec 2000 09:41:33 GMT
http://axion.physics.ubc.ca/cbw.html
------------------------------
From: "lowtus" <[EMAIL PROTECTED]>
Subject: How does public key crytography work, mathematically?
Date: Sat, 16 Dec 2000 04:06:04 -0600
Reply-To: [EMAIL PROTECTED]
I purchased applied cryptography, and I've been reading it thoroughly,
and while doing so, I've pondered the creation and programming/math
involved in encryption. Symmetrical keys make perfect sense to me. If
f(x) = character * key simply solve for key. But I don't understand how
there can be a public key for encrypting and private key for decrypting
that both generate non-gibberish.
To acheive this, I am assuming that the encryption/decryption algorithms
are different where the key is applied. Applied Cryptography suggests to
assume that the source of your program is available, so wouldn't someone
simply be able to look at your two equations and derive one key from the
other? That can't be right though... How does it work?
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: binary vs. text w/ regard to digital signatures
Date: 16 Dec 2000 10:55:53 +0100
In article <[EMAIL PROTECTED]>, Marc <[EMAIL PROTECTED]> wrote:
>> The fact that tilde-n has one and only one encoding does not help use
>> avoid the fact that two different sequences have precisely the same
>> visual effect.
>
> In many fonts the 0 and O (digit zero and uppercase o) have the same
> visual effect, too. Like for example the one I am typing with.
Likewise the 1 and l and I (digit one, lower-case L and upper-case i)
are quite similar.
This can be a real problem if you're supposed to enter a password
someone has written wodn, and the password contains both lowercase
and uppercase characters and digits: 0 can then be confised with
O, and 1, l and I can all be confused with one another. Suppose your
password is e.g.:
O10lI10OIOlO1Ol010l0IO1
Now, try to type THAT from a printout, without errors....
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Visual Basic Source Code
Date: 16 Dec 2000 10:54:11 +0100
In article <3a3aa1bf$0$17722$[EMAIL PROTECTED]>,
Jason Bock <[EMAIL PROTECTED]> wrote:
> Simon Best <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>> I recognise this stereotype of VB programmers as generally not being
>> programmers. It's a stereotype even held by some managers who don't
>> have anything to do with programming! (I came across this from an
>> economist/accountant/management friend, who's description of VB
>> programmers was that they were 'just playing with Lego', mentioning that
>> they had to contract out to get any real software guts written.)
>>
>> While the stereotype may well not be universally applicable to all who
>> use Visual Basic, it does seem that there are a surprisingly large
>> number of VB 'programmers' who do fit the stereotype. A more
>> appropriate description might be 'graphical user interface designers'
>> (as even the programming for that is done for them).
>
> On this I will agree, and that's where I think the stereotype comes from.
> It's not the language or the tool - it's the ones who have latched on.
Don't you think the two of them are at least somewhat correlated?
> Unfortunately, VB makes it so easy to create programs any yahoo can come
> along and call themselves a "developer" (or a consultant, heaven forbid
> ;) ). I've been involved in 3 different projects where I had to take
> someone's VB code base and either maintain it or substantially enhance it.
> None of them were fun.
>
> That said, in the hands of someone who knows what they're doing, it's not
> all that bad ;).
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Visual Basic Source Code
Date: 16 Dec 2000 10:52:50 +0100
In article <3a3a3338$0$90271$[EMAIL PROTECTED]>,
Jason Bock <[EMAIL PROTECTED]> wrote:
> Paul Schlyter <[EMAIL PROTECTED]> wrote in message
> news:91cp0a$78c$[EMAIL PROTECTED]...
>
>> In article <3a39a408$0$75795$[EMAIL PROTECTED]>,
>> Jason Bock <[EMAIL PROTECTED]> wrote:
>>
>>> People have done some amazing things in VB to break beyond its'
>>> boundaries (i.e. they don't fear "real programming").
>>
>> If they don't fear "real programming", why don't they switch to some
>> real programming language?
>
> First, define "real programming language." What are you criteria?
A language which doesn't get in the way for what you want to do even
if you want to do less common things, e.g. implement crypto
algorithms, or an operating system.
> What makes VB not a "real programming language"?
Ever tried to e.g. build an OS in VB? No? Why not?
BTW below you argue that VB isn't even a programming language at all.
So don't you agree that something which isn't a programming language
definitely cannot be a real programming language?
> BTW, technically VB isn't a language, it's a tool (I admit in this
> thread I've been calling it a language, but it's more of a
> language/tool combo).
VB has a syntax which compiles in some sort of executable code.
That makes it a language. Of course all languages are tools.
> You type in some code, you compile it, it runs on a Windows-based
> workstation. I fail to see how that disqualifies it from being a
> "real programming language."
A real programming language can do more than just build everyday
bread-and-butter applications. Ever tried to build an OS in VB? Or
a crypto library of the most common encryption algorithms? Or a
bignum library? It's stuff like that you need real programming
languages for, instead of toy programming languages.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: Visual Basic Source Code
Date: 16 Dec 2000 10:53:40 +0100
In article <3a3a348d$0$90273$[EMAIL PROTECTED]>,
Jason Bock <[EMAIL PROTECTED]> wrote:
> Paul Schlyter <[EMAIL PROTECTED]> wrote in message
> news:91cov5$75j$[EMAIL PROTECTED]...
>> In article <3a39a2f0$0$75802$[EMAIL PROTECTED]>,
>> Jason Bock <[EMAIL PROTECTED]> wrote:
>>
>>> I'm not advocating VB - I'm interesting in why someone dismisses VB
>>> outright.
>>
>> Mainly because of three reasons:
>>
>> 1. VB is based on BASIC, a programming language which ought to have
>> become extinct long ago. But thanks to Bill Gates it's still here,
>> more widespread than ever. Bill Gates once started out with BASIC
>> (he wrote the first BASIC interpreted for the Mits Altair back in
>> 1976 or so), and he returned to BASIC, incarnated as VB, ASP,
>> WordBasic and possibly something else as well. "Basic forever".....
>
> You need to do your homework on this one. First, saying that BASIC
> "ought to have been extinct long ago" is purely a matter of opinion.
It's an opinion, yes, but it's a well-founded opinion. E. Dijkstra
expressed this decades ago: "The teaching of BASIC, in schools,
should be considered a criminal act!" -- admittedly that opinion is
somewhat extreme. Beginner's All Symbolic Instruction Code (=BASIC)
does has its use though, as an easy introduction to simple
programming for people who won't become programmers.
> Many people think C++ should die in flames as well.
If these people got it their way, they'd lose VB at the same time,
since the VB programming environment most likely was implemented
in C++ to a large part.
> Others hate Perl. Some eschew Eiffel. But that doesn't disqualify
> the language in itself.
That depends on hos well-founded these opinions are.
> Also, ASP is NOT BASIC. You need to look at ASP harder. You can use any
> scripting language in ASP, just as long as you have the correct interpreter.
You are right on that one -- I did confuse ASP with VBscript. OTOH most
ASP code I've seen do use VBscript.
>> 2. VB is non-standard
>
> So? Neither are a lot of languages. Doesn't bother a lot of people.
I'm fully aware that this doesn't bother a lot of people, but those
who later will want to port their code will then regret their earlier
ignorance.
> BTW define "standard."
Approved by ISO, ANSI and similar standards bodies.
> I know, submit it to ECMA or any other standards committee.
AND have them approve it! Many proposed standards never make it
to actually becoming a standard. About a year ago, Java was withdrawn
from the just s tarted standardisation process -- apparently Sun
wants to "own" the language some more years.
> I fail to see why that excludes VB as it is not a standard
OK, I should really have said instead:
2. VB is a single-platform language
Actually some non-standard languages are multi-platform. One example
is Java, which although it's formally nonstandard does have a
de-facto standard anyway (Sun's implementation), which other
implementors try to follow. Except Microsoft of course, which
call their Java-like janguage "J++".
> (there are many other languages that are not "standard").
True. Fortunately, most of them aren't widely used. And if
a language has a very special purpose, it may be sensible to
not bother standardising it.
>> 3. VB is non-portable
>
> Again, that's a personal taste.
No, that's not "personal taste"; that's a fact. Try to port a
VB application to a non-Microsoft platform !!!
> I could care less if my VB app isn't portable. There are
> cases where you need to be portable - use Java which
> claims to be WORA. But I've run into that kind of situation
> so infrequently in my career, and I would argue that such a
> need isn't as big as some industry experts claim it to be.
Perhaps your career is so short that you haven't yet experienced any
major switches in OS preferences?
When your favourite OS gets old fashioned and you're forced to
move on to another OS, it's a pity if you must throw away all that
software for your old OS, isn't it?
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pausch at saaf dot se or paul.schlyter at ausys dot se
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Nonlinear Diffusion with S-Boxes?
Date: Sat, 16 Dec 2000 10:22:24 +0000
Hello!
Bet this is old hat to many here, but I only had this realisation a few
days ago (in another discussion).
I was wondering on doing bits of diffusion using nonlinear S-boxes in
the following way:
a0, a1: Initial words (all words the same size)
b0, b1: Final words
t0, t1: Temporary words
S-box: A wordsize by wordsize S-box
t0 = a0 xor a1
b0 = a0 xor S-box[t0]
b1 = a1 xor S-box[t0]
Deriving the inverse:
t1 = b0 xor b1
= a0 xor S-box[t0] xor a1 xor S-box[t0]
= a0 xor a1
= t0
That's t0 recovered...
c0 = b0 xor S-box[t0]
= a0 xor S-box[t0] xor S-box[t0]
= a0
That's a0 recovered, and a1 can be recovered in the same way.
An inverse of the S-box isn't needed, so the S-box doesn't need to be
bijective (though I can imagine a nonbijective (unijective?) S-box would
reduce diffusion).
What struck me as neat about this is that it can combine nonlinearity
with diffusion, and it's an involution (it is it's own inverse).
Thinking about it further, I ended up with an idea of a block cipher
round using this. It exclusively uses one function:
f( a0, a1 ) = S-box[ a0 xor a1 ]
With a round key the same size as the block, and the block arranged as a
two dimensional array of words with two rows (and the key likewise, if
you like):
w0 w1 w2 w3 w4 w5 w6 w7
w8 w9 wA wB wC wD wE wF
(16 words for this example.)
1. Apply function f to corresponding block and key words, putting the
results in the block:
w0' = f( w0, k0 ) = S-box[ w0 xor k0 ]
(Nothing new there!)
2. Apply function f to the words of each column of the block, putting
the results in a temporary row (the same size as a block row):
t4 = f( w4, wC )
3. Apply function f to the temporary row and the block's top row,
putting the results in the top row:
w3 = f( w3, t3 )
4. And again, but with the bottom row of the block:
wB = f( wB, t3 )
That's key addition, nonlinear word substitution, and nonlinear word
pair diffusion done using just one function! (Of course, transposing
the words between such rounds would obviously be necessary to get the
whole block to diffuse (hypercubic? I like hypercubes, they're easy).)
Anyway, any thoughts? Comments? Confirmation that this is indeed old
hat? Worth using as part of a block cipher? Fatally flawed from the
outset?
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: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: How does public key crytography work, mathematically?
Date: Sat, 16 Dec 2000 10:25:35 GMT
lowtus wrote:
>
> I purchased applied cryptography, and I've been reading it thoroughly,
> and while doing so, I've pondered the creation and programming/math
> involved in encryption. Symmetrical keys make perfect sense to me.
> If f(x) = character * key simply solve for key. But I don't
> understand how there can be a public key for encrypting and private
> key for decrypting that both generate non-gibberish.
>
> To acheive this, I am assuming that the encryption/decryption
> algorithms are different where the key is applied. Applied
> Cryptography suggests to assume that the source of your program is
> available, so wouldn't someone simply be able to look at your two
> equations and derive one key from the other? That can't be right
> though... How does it work?
Consider RSA encryption:
Let p, q be two large primes.
Let phi be the LCM of p-1 and q-1.
LCM means least common multiple.
Pick e such that 1 < e < phi, and GCD( e, phi ) = 1
GCD is greatest common denominator.
Let d be the modular inverse of e, mod phi.
Use the extended Euclidean algorithm for this.
pq and d are the public key.
Yes, I mean the product of p and q.
pq and e are the private key.
It is impossible to get d from e without phi
-- or equivilantly, p and q
Encryption is done by treating the message, m, as a large inter, and
raising it e power, modulo pq. Decryption is done by treating the
ciphertext, c, and raising it to the d power, modulo pq.
If you factor pq, you can break the system.
If you can find the (e)th root of the ciphertext, under mod pq, you can
also break the system.
Because these are both difficult, the system is considered secure.
--
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: Simon Best <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: How does public key crytography work, mathematically?
Date: Sat, 16 Dec 2000 11:00:00 +0000
lowtus wrote:
>
> I purchased applied cryptography, and I've been reading it thoroughly,
> and while doing so, I've pondered the creation and programming/math
> involved in encryption. Symmetrical keys make perfect sense to me. If
> f(x) = character * key simply solve for key. But I don't understand how
> there can be a public key for encrypting and private key for decrypting
> that both generate non-gibberish.
I believe they're called 'trapdoor one-way functions', but I know little
about them. There's a way to encrypt with the public key that's easy,
but decrypting isn't possible with the public key: it's a one-way
function. Decryption uses the private key, which is related to the
public key in such a way that it provides a quick way to undo the
encryption, which is why encryption was a trapdoor one-way function
after all. (That's almost everything I know about this.)
> To acheive this, I am assuming that the encryption/decryption algorithms
> are different where the key is applied. Applied Cryptography suggests to
> assume that the source of your program is available, so wouldn't someone
> simply be able to look at your two equations and derive one key from the
> other? That can't be right though... How does it work?
As well as the private and public keys being related to each other in a
way that's related to how decryption and encryption are related, the
private and public keys need to be related by a one-way function
themselves. It needs to be too difficult or time consuming to get the
private key from the public key, so it needs to be quick and easy to get
the public key from the private key.
For example, multiplying two large prime numbers is good, 'cause
factorising a large number into prime factors is a time consuming thing
indeed! The two primes would be the private key, and the product would
be the public key. RSA uses this kind of factoring problem thing.
I hope I've shed a little light on some of the landscape...
Simon
--
_______________________________________________________________________________
Personal: [EMAIL PROTECTED]
Yellow Skies: [EMAIL PROTECTED] http://www.yellowskies.com
Everyone does their own signature to be different. How does that work?
------------------------------
** 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
******************************
