Cryptography-Digest Digest #355, Volume #13 Sun, 17 Dec 00 16:13:00 EST
Contents:
Re: Q: Result of an old thread? (Walter Hofmann)
Re: Q: Result of an old thread? (Walter Hofmann)
Re: Protocol for computer go (Marc)
Re: Custom Encryption Algorithm (Marc)
Re: Visual Basic Source Code ("Jason Bock")
Re: Visual Basic Source Code ("Jason Bock")
Re: Visual Basic Source Code ("Jason Bock")
Re: Visual Basic Source Code ("Jason Bock")
Re: Protocol for computer go (David Wagner)
Mathematical concepts ("Joris Vankerschaver")
Re: Q: Result of an old thread? (Mok-Kong Shen)
Use of multiplexing (Mok-Kong Shen)
Re: Silly question ("Cameron Wickham")
Re: Silly question ("Cameron Wickham")
Re: Mathematical concepts ("M.S. Bob")
Re: Mathematical concepts (David A Molnar)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Walter Hofmann)
Subject: Re: Q: Result of an old thread?
Date: Sun, 17 Dec 2000 18:00:00 +0100
On Sun, 17 Dec 2000 06:15:16 GMT, Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>
>I'm confused. Please tell me how a limit is defined when a discrete
>valued finite field is used.
I wasn't speaking about finite fields.
Surely the only reasonable (ie. Haussdorff) topology on a finite filed
is the discrete one, so a sequence converges iff it is eventually
constant.
Walter
------------------------------
From: [EMAIL PROTECTED] (Walter Hofmann)
Subject: Re: Q: Result of an old thread?
Date: Sun, 17 Dec 2000 18:03:28 +0100
On Sun, 17 Dec 2000 16:39:24 +0100, Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>If, as you say, it 'diverges', how could the end result
>'converge'? Do you mean that if first diverges and then
>converges as epsion->0? How do you know that? If that
>were the case, what would happen at the turning point
>between divergence and convergence? Does such a point
>exist?
Consider
f: R-->R, x-->1/x
f diverges near 0, but
g: R-->R, x-->f(f(x))
converges near 0 (because g is the identity except for being undefined
at zero; this is exactly the situation we are in).
Walter
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: Protocol for computer go
Date: 17 Dec 2000 18:41:12 GMT
(tokenized programs running on an interpreter)
>Interesting approach. Might be practical if some sponsor provides
>hardware running the tokenized language at lightning speed to run
>the tournament on. Sun, are you listening ?
The tournament doesn't necessarily have to run in real time. The
(then valid) instruction counter can be used for comparision among
the participants, and a 2001 tournament can have a 100 Giga
instructions limit for 1 game, while the 2002 tournament can have a
limit of 150 G to compensate for the progress with hardware.
I think this approach opens a way to a working solution for the
requirements listed. (not only because of the cycle counting
issue, but also for the forbidden covert channels etc).
It is an academic challenge however, because no participant
can spend more dollars on a better hardware to gain
an advantage over the competition. Nothing like IBM versus
Kasparov.. Also, the results of the competition do not
directly map into the real world. The algo that was found
to be "best", might perform less optimal when ported to
ANSI-C for C16x in a hi-tech breadboard game for kids.
(Much like compilers are tweaked to compiler benchmarks, the
games might be tweaked towards the specialities of the interpreter
programming language).
But it allows for an academic evolution of algorithms which
compete against each other in a defined environment. Which is
what I think the poster intended with his question. (?)
Hm, does anyone remember the concept of COREWARS?
------------------------------
From: [EMAIL PROTECTED] (Marc)
Subject: Re: Custom Encryption Algorithm
Date: 17 Dec 2000 18:41:17 GMT
>Heh heh heh... well, I appreciate the input. However, my question would
>be this: why in the world would I give you plaintext/ciphertext pairs,
>or information about its architecture, or any other clues whatsoever?
Because in most real-world scenarios the real attacker HAS knowledge
of the algorithm used.
If you encrypt your harddisk, and I steal your computer, I have
your crypto-IDE-controller and can read its BIOS rom and disassemble
it. I then know the algorithm and only your password (key) is absent.
If you write a game that encrypts the highscores, I disassemble it
and know the algorithm.
If you are a bank and protect the atm cards with your algorithm, I
pay a couple of mafia gansters to steal one of your atm machines,
then I take out the chips, bring them to a chip factory in korea
and have the protected rom read out. I then disassemble it and
know the algorithm.
(or, I steal an internal phone directory of your bank and start
to bribe any of your tech employees until one of them tells me about
the algorithm)
If you use it to communicate privately with your business partners,
I select the weakest of them (least security-aware), break into
his rooms at night and steal the program. I then disassemble it
and know the algorithm.
Do you get the idea? In most - if not all - cases, the REAL-WORLD
attacker has a chance to learn about your algorithm. If you want a
real-world test of the strength of your algorithm, you must apply
real-world conditions to the test.
That includes to release the algorithm to the contest participants.
(And even then the motivation to crack it is lower than in real-world,
because the financial win that an attacker expects is absent. You
can compensate for that by giving a price, eg $10,000 US, for the
first to crack your algorithm).
You might say "I protect only 1 cent worth of information with it
and nobody will break into my home for 1 cent" and you are right
with that. But at the same time you confess that your algorithm is
not worth anything more than 1 cent.
Then you have judged the strength already yourself, and the query
to sci.crypt is obsolete.
Your challenge reminds me of the Deutsche Telekom, a provider of
GSM mobile service. When COMP128 (the algorithm used to protect
the customer identify on the SIM card) was cracked, the Deutsche
Telekom announced a challenge. They put a brand-new, never used
SIM card into a safe at a lawyers bureau. Then they asked any
hacker to try to make a "free" phone call on that cards' account.
The hacker only knows the phone number. They promised a price
of 100,000 DM (approx $50,000 US), which are not paid to the
successful hacker but instead to a social organization to be named
by the hacker.
This drops out all attacks and is therefore not a fair challenge.
a) you can not "clone" the card because you don't have physical
access to it. In real world you could steal a mobile and
return it back later the day.
b) you can not receive radio messages emitted from a mobile with
this card because it is not on-air (it's in the lawyers safe).
In real-world, the air is full of radio messages from millions
of mobiles, and you can even impersonate a base station and
have a mobile react on your commands (eg perform COMP128
authentications for you over the air).
c) the almost-always-working man-in-the-middle attacks fail too
because the mobile is not on-air, unlike the real-world users.
d) the motivation to crack the card is only for fame, because
the money will not be given to the hacker. The investment
to crack it is lost. A business with negative saldo.
Cloning a real-world sim is more profitable than cracking
the challenge sim.
Basically, this challenge SIM card is protected far better than
any SIM card issued to real customers. Obviously the Deutsche
Telekom is not confident enough about their security to
challenge the hacker community to abuse chairman Ron Sommers'
mobile or something similarily appropriate.
Your challenge has similar flavors and seems not to be realistic.
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Sat, 16 Dec 2000 14:40:29 -0600
<[EMAIL PROTECTED]> wrote in message
news:jQM_5.3315$[EMAIL PROTECTED]...
> Paul Schlyter <[EMAIL PROTECTED]> wrote:
> > 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.
>
> ARGH! Yes, that's it, just ARGH! ;)
>
> You ever try and build an OS in cobol? What about python? sh? perl?
> forth, pascal, logo, prolog, fortran?
>
> Seriously, are we to conclude that _all_ of those are also imaginary
> programming languages because they're less suited to writing operating
> systems than C? Or is your argument basically that hammers are
> intristically better tools than screwdrivers, because you can also
> pound screws into wood at a slower rate with more effort using one?
Thank you. Couldn't have said it better myself ;).
Jason
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Sat, 16 Dec 2000 14:42:54 -0600
Simon Best <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Because BASIC makes it so easy to do things very badly, and get in a
> hideous mess
I think this is a matter of opinion. C and Perl can lead to some of the
most twisted code I've ever seen. Then again, I've seen elegant code with
those languages as well. Likewise with BASIC. It's not the language, it's
the programmer who uses the language that really makes the difference.
Jason
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Sun, 17 Dec 2000 12:53:22 -0600
Sigh...can't seem to leave this alone.
Paul Schlyter <[EMAIL PROTECTED]> wrote in message
news:91i7t7$evc$[EMAIL PROTECTED]...
> In article <3a3b9fe8$0$90278$[EMAIL PROTECTED]>,
> Jason Bock <[EMAIL PROTECTED]> wrote:
> > It's not ignorance. I know full well that VB is controlled by MS. But
> > that doesn't bother me for the tasks at hand.
>
> Why are you so uninterested in having your code somewhat more
> portable? Do you know in advance that your code will be so ephemeral
> that porting it will never become an issue?
I never said I wasn't uninterested. Stop putting words into my mouth - you
said you didn't like that either.
There are situations where it's needed, and other times it's not. That's
the way I've seen it. There are more pressures in software development that
programming in a "real programming language."
> >>>> 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 !!!
> >
> > That's not what I was trying to say. What I meant by "personal
> > taste" is that, given a certain situation, it simply doesn't
> > matter that something is portable.
>
> Very true -- sometimes it does not matter. For instance when:
>
> 1. your programming project is a failure -- no-one would be
> interested in porting such code.
>
> 2. your code will have a lifetime so short that you'll know it'll be
> obsolete when a different OS or environment becomes popular.
Or, the project is a prototype, or the project doesn't have the lifetime of
years on end, etc., etc. Some projects don't live 20 years - sorry if you
haven't seen this.
> > Sigh. OSes come and go, and I'll make the change. Of course, if we all
> > wrote code in standard ANSI C++, the world would be perfect, right?
Ain't
> > going to happen, ever. Tools will come and go. OSes will come and go.
> > Languages will come and go. If we could all just use one OS and one
> > language, this wouldn't be an issue. But that's never going to happen.
The
> > key in my mind is that the communication between n systems is the same.
> > Because this industry changes so much, that's about the best you can do.
>
> Perhaps that's a strategy to make sure you'll get jobs in the future:
> make sure your applications are short-lived and need to be rewritten
> from scratch once every few years..... <g>
You can think that. Change happens irregardless of what I want to do or
not. I don't pretend to have such control over the industry as a whole.
> Now imagine if these principles were applied to other industries:
>
> a) you could only live in your house only for a few years, because
> after that it would break down and would need to be rebuilt. No,
> there's nothing you can do about that, that's just the way it is.
> No builders want to build more endurable buildings, because if
> they did, there would be too few jobs for them in the future.
>
> b) all your electrical appliances would need to be replaced every
> few years or so. Today they run on 100 Volts, but next year
> there's be an upgrade to 220 Volts, and a few years later to
> 400 Volts. In between there'll be switches between 50 c/s,
> 60 c/s, 100 c/s and DC !!!
>
> c) The new Car-2000 you bought yesterday cannot be driven because
> it's incompatible with today's highway's -- you'll need to wait until
> the Highway-2000 system has been opened -- unfortunately it's late
> but it'll open "real soon now".... but that's OK really, because
> then you'll have time to upgrade to Drivers-License-2000, since
> your current driver's license won't authorize you to drive Car-2000....
>
> Just imagine.....
Yep. Happens all the time in this industry. Are you going to stop it?
Other industries are different. People buying a house won't tolerate having
their house broken down in three years. The computing industry simply
hasn't fought back enough to force stability. But then again, I don't see
that happening for a long time. The industry allows you to change things at
a very rapid rate, much faster than building a house.
Of course, building software does have a lot of analogies to building a
house. But I just don't see things slowing down for a while. I can either
fight to stay on one OS using one language for the rest of my life, or I can
decide to watch where things are going and make career changes based on such
observations.
Jason
------------------------------
From: "Jason Bock" <[EMAIL PROTECTED]>
Subject: Re: Visual Basic Source Code
Date: Sun, 17 Dec 2000 12:44:56 -0600
The only reason I'm responding is this:
Paul Schlyter <[EMAIL PROTECTED]> wrote in message
news:91i7qq$erk$[EMAIL PROTECTED]...
> In article <3a3b8e0e$0$17731$[EMAIL PROTECTED]>,
> Jason Bock <[EMAIL PROTECTED]> wrote:
> > Yes. See
> >
<http://www.devx.com/premier/mgznarch/vbpj/2000/03mar00/bb0300/bb0300.asp>.
> > You may not have Premiere access to view this on DevX's site, but it's
the
> > Black Belt article in the March 2000 issue of VBPJ.
>
> You don't have an URL to an article which is accessible?
Yell at DevX. It's their decision to make it at Premier level access -
that's something that I can't control. But you wanted proof - the proof is
there.
Jason
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Protocol for computer go
Date: 17 Dec 2000 18:59:59 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
This is all very easily fixed (in principle) by measuring time
in terms of an instruction count (which *is* a deterministic function
of the transcript) rather than in terms of real wall clock time
(which is *not* a deterministic function of the transcript).
------------------------------
From: "Joris Vankerschaver" <[EMAIL PROTECTED]>
Subject: Mathematical concepts
Date: Sun, 17 Dec 2000 19:47:38 +0100
Hello
I'm terribly sorry if I'm asking a question that has been asked some
times before, but I did quite some searching and I'm getting desperate.
I'm reading "Applied Cryptography" now. It's a great book, but can
anyone recommend a good maths book on cryptography? I've studied finite
fields, rings and such things in uni so it doesn't really have to be that
basic (I suppose).
So what I'm looking for is a book that approaches cryptography from a
more mathematical point of view, preferably with some of those
prime-generating methods in detail....
With kind regards,
Joris
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Q: Result of an old thread?
Date: Sun, 17 Dec 2000 20:41:20 +0100
Walter Hofmann wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >
> >If, as you say, it 'diverges', how could the end result
> >'converge'? Do you mean that if first diverges and then
> >converges as epsion->0? How do you know that? If that
> >were the case, what would happen at the turning point
> >between divergence and convergence? Does such a point
> >exist?
>
> Consider
>
> f: R-->R, x-->1/x
>
> f diverges near 0, but
>
> g: R-->R, x-->f(f(x))
>
> converges near 0 (because g is the identity except for being undefined
> at zero; this is exactly the situation we are in).
If I understand you claim, your procedure is applicable to
any singlular matrix, isn't it? In that case one would
be able to 'define' an inverse of any singular matrix,
namely via the (supposedly unique) limit obtained from
your procedure. Do you want to claim that?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Use of multiplexing
Date: Sun, 17 Dec 2000 20:44:46 +0100
Multiplexing is a rather old topic in CS. In the crypto
context, it is also well-known (see spread spectrum, CDMA).
I like to consider the issue presently, however, purely
at the application level, i.e. whether a normal user, who
does encryptions as usual, can profitably apply multiplxing
techniques of his own.
In plenty of situations one does not send occassionally
single messages. Between two distant officies of a
commercial firm, for example, a substantial amount of
communications, usually of different security levels,
occur. It is thus feasible to multiplex the messages,
i.e. intermingling them in some secret (either fixed or
dynamically varying) way that is unknown to the opponent,
thus rendering his analysis job difficult. There will
certainly be some appreciable cost/work involved for
the partners doing multiplexing, but the resulting
difficulty caused to the opponent could under circumstances
justify that, I believe. I wonder thus whether such
multiplexing has not already been successfully employed in
practice.
We note that multiplexing can be done at two different
levels, (intermingling of plaintexts and of ciphertexts),
and also at different granularity (word/byte/bit).
M. K. Shen
=============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Cameron Wickham" <[EMAIL PROTECTED]>
Subject: Re: Silly question
Date: Sun, 17 Dec 2000 20:11:56 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Does the chinese remainder theorem work for polynomials over GF(2)?
>
Yes. In fact, it works for polynomials (in one variable) over any field. A
polynomial ring in one variable over a field is a Euclidean domain and the
CRT holds if the ring you are working in is Euclidean. I think it works if
the ring is only a principal ideal domain, but I'm not 100% sure and I'm too
lazy to work it out right now.
--
Cameron Wickham
[EMAIL PROTECTED]
------------------------------
From: "Cameron Wickham" <[EMAIL PROTECTED]>
Subject: Re: Silly question
Date: Sun, 17 Dec 2000 20:20:32 GMT
"Dido Sevilla" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Well, the only way to verify it is to actually go through the motions of
> the proof, using the properties of GF(2)[x] instead of Z. Another way
> is to prove it is to prove that the ring of polynomials with
> coefficients in GF(2) is isomorphic to Z. I think that the two rings
> are isomorphic if you consider the map from GF(2)[x] -> Z where you'd
> evaluate the polynomial in GF(2)[x] as though it were a polynomial in
> Z[x] at the value 2.
These two rings are not isomorphic. A quick way to see this is that Z has
characteristic 0, whereas GF(2)[x] has characteristic 2. Isomorphic rings
must have the same characteristic. I think the map you describe is a
bijection from GF(2)[x] to the nonnegative integers obtained by writing each
nonnegative integer as a sum of powers of 2, i.e., it's binary expansion.
--
Cameron Wickham
[EMAIL PROTECTED]
------------------------------
From: "M.S. Bob" <[EMAIL PROTECTED]>
Subject: Re: Mathematical concepts
Date: Sun, 17 Dec 2000 20:38:31 +0000
Joris Vankerschaver wrote:
>
> So what I'm looking for is a book that approaches cryptography from a
> more mathematical point of view, preferably with some of those
> prime-generating methods in detail....
_Cryptography: Theory and Practice_ by Douglas Stinson
CRC Press; ISBN: 0849385210
_A Course in Number Theory and Cryptography_ by Neil Koblitz
Springer Verlag; ISBN: 0387942939
_Algebraic Aspects of Cryptography_ by Neil Koblitz
Springer Verlag; ISBN: 3540634460
For more of a reference, not a textbook:
_Handbook of Applied Cryptography_ by by A. Menezes, P. Van Oorschot,
S. Vanstone
CRC Press ISBN: 084938523
online PDFs of text at http://www.cacr.math.uwaterloo.ca/hac/
Koblitz's _A Course in Number Theory and Cryptography_ includes a good
chapter on primality and factoring.
_Prime numbers and computer methods for factorization_ by H. Riesel, or
_The new book of prime number records_ by P. Ribenboim are two good yet
accessible sources about testing primality.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Mathematical concepts
Date: 17 Dec 2000 20:42:56 GMT
Joris Vankerschaver <[EMAIL PROTECTED]> wrote:
> So what I'm looking for is a book that approaches cryptography from a
> more mathematical point of view, preferably with some of those
> prime-generating methods in detail....
You will find the algorithms for prime generation (as well as some of the other
details glossed over in _Applied Crypto_) in the _Handbook of Applied
Cryptography_, which is available online.
The _Handbook_ has no proofs, however. For a book with proofs, you may consider
Stinson's _Cryptography : Theory and Practice_. It covers prime generation in a
bit more detail than Koblitz _A Course in Number Theory and Cryptography_
(in particular, it includes a very clear exposition of why Rabin-Miller's
probability of failure isn't quite 1/4 despite "what everyone thinks"); on
the other hand, Koblitz has an introduction to factoring algorithms and elliptic
curve cryptography.
Maybe of interest if you're coming from a math background would be Koblitz
_Algebraic Aspects of Cryptography_. I have not read this book, but I know it
covers more advanced elliptic curve material and other fun groups for
cryptography.
If you want more detail on number theory, a good place to start is Bach &
Shallit _Algorithmic Number Theory vol 1 : Efficient Algorithms_. Covers a
wide range of material, including analytic number theory results on the
density of primes, distribution of primes, and so on. Really a good book.
I wish I could justify buying a copy, but I don't have time to read it right
now.
After that, Henri Cohen's _A Course in Computational Algebraic Number Theory_
should keep you busy for a while. Includes such things as the LLL lattice
basis reduction algorithm, the Kilian-Goldwasser primality test and later
enhancements, and more things to do with polynomials than you thought possible.
I find it rough going, but I'm just an undergraduate - your mileage may vary.
thanks,
-David
------------------------------
** 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
******************************
