Hi,
sorry for taking this off-list earlier.
> > 1) "Modern cryptography uses many fundamental concepts from number
> > theory"
> >
> > I think the precise statement would be that public key cryptography uses
> > many fundamental concepts from number theory. Most of symmetric
> > cryptography is not based on a computational (perceived) hard
> > mathematical problem.
>
> When I wrote that statement, I was also thinking of hardware
> implementation as well, such as using the Chinese Remainder Theorem for
> efficient arithmetic at the hardware level, etc. Of course in this
> sense, any computation that involves hardware uses hardware
> implementations of fundamental concepts from number theory.
But most symmetric cryptography constructs don't use big numbers: most block
ciphers, most stream ciphers, most hash functions. They are designed for
speed and avoid bigint arithmetic where possible. Of course, there are a few
exceptions but AFAIK they are not used in practice.
> Since you've
> made a distinction above between public key and symmetric cryptography
> (without explicitly appealing to hardware implementation), I think I
> should make the following change in order to avoid confusion on the part
> of readers:
>
> -"Modern cryptography uses many fundamental concepts from number theory"
>
> +"Public key cryptography uses many fundamental concepts from number
> theory"
>
> > 3) "How to keep a secret"
> >
> > This section seems to give an example for encoding a message and not
> > encryption. The encoding provides no security at all. You probably know
> > that but it might make sense to point it out very explicitly.
>
> This tutorial is mostly for folks who don't have prior
> knowledge/experience with cryptography. In particular, students who are
> taking a first course in cryptography at the undergraduate level can use
> this tutorial while doing so. I did mention that it's "a simple method
> of scrambling a message written in English". But it wouldn't hurt anyone
> to also clarify the relative cryptographic insecurity of that "simple
> method".
I might be a bit pedantic but this scrambling has less than relative
insecurity, it doesn't provide any. I think being somewhat precise this issue
is worth it because:
- people who read the tutorial but who are familiar with basic cryptology
don't get the wrong impression that "the Sage folks" don't know what they are
talking about
- students don't get the wrong impression that coming up with encryption
algorithms is straight-forward.
For fun, here's the 'attack' if one doesn't recognise the ASCII directly:
sage: s = "Sage can be used to study general and advanced, pure and applied
mathematics. This includes a huge range of mathematics, including algebra,
calculus, elementary to very advanced number theory, cryptography, numerical
computation, commutative algebra, group theory, combinatorics, graph theory,
exact linear algebra and much more. It combines various software packages and
seamlessly integrates their functionality into a common experience. It is
well suited for education, studying and research. The interface is a
notebook in a web-browser or the command-line. Using the notebook, Sage
connects either locally to your own Sage installation or to a Sage server on
the network. Inside the Sage notebook you can create embedded graphics,
beautifully typeset mathematical expressions, add and delete input, and share
your work across the network. The following showcase presents some of Sage's
capabilities, screenshots and gives you an overall impression of what Sage
is. The examples show the lines of code in Sage on the left side, accompanied
by an explanation on the right. They only show the very basic concepts of how
Sage works. Please refer to the documentation material for more detailed
explanations or visit the library to see Sage in action."
sage: s = map(ord,s)
sage: from rpy import r
sage: r.png('histogram.png',width=900,height=480)
sage: r.hist(s,r.seq(min(s),max(s)),main="Histogram",col="lightblue",
prob=True, xlab="orders")
sage: r.dev_off()
The Basic Cryptanalysis US Army Field Manual (aka the Cryptonomicon ;-)) has a
nice introduction http://www.umich.edu/~umich/fm-34-40-2/ :-) Stinson's book
is a good (and civil) reference. I'm not implying you don't know all this,
I'm just pointing it out in case someone else on [sage-devel] doesn't.
> > 4) Generating public and private keys
> >
> > Choosing p and q of such different sizes is really a bad idea and IMHO
> > shouldn't be encouraged. The hardness of factorisation depends on the
> > size (and form) of the smaller factor.
>
> Technically, you're right. But again, this tutorial is for Sage
> beginners and, I also assume, folks doing cryptography for the first
> time. I can write about special attacks against RSA, but that would
> increase the page count of the tutorial. Remember, we want "short"
> tutorials to introduce Sage beginners to various features of Sage. For
> more in-depth information, there's the official reference manual as well
> as the source code. I've provided references if readers want more stuff
> on cryptography or Sage. Furthermore, at the beginning of the tutorial,
> I've provided various avenues for obtaining more help.
I agree with William here that at least a note should be added that this
construction is insecure and for education purposes only.
> which is short, elegant and Pythonic. The tutorial has now been updated
> with the above code --- and I hope it doesn't result in too much
> confusion on the part of beginners.
What is the general opinion on this matter? Is it fine to suppose some
knowledge of Python?
> > 6) "Brute force modular exponentiation"
> >
> > What is brute force modular exponentiation? Do you mean naive
> > exponentiation over ZZ?
>
> Yep, like trying to naively compute a^b first, then reduce modulo n.
Brute force sounds like trial-and-error to me.
> > Also note that if you just create the IntegerModRing (the Sage way) then
> > exponentiation just works as it should:
> >
> > sage: R = IntegerModRing(1000)
> > sage: e = R.random_element()
> > sage: e^3423523523513513513513524643636
> > 81
>
> Yep, but any element from R.random_element() is not guaranteed to be
> relatively prime to 1000, for example. We can do this:
>
> sage: n = 4951760154835678088235319297
> sage: N = IntegerModRing(euler_phi(n))
> sage: e = N.random_element()
> sage: gcd(Integer(e), euler_phi(n))
> 3
>
> But what we require is some positive $e \in Z$ that is relatively prime
> to $\phi(n)$. Then we'd still need a test for relative primeness with
> respect to $\phi(n)$. OK, no problem, how about this:
>
> [2]
> sage: n = 4951760154835678088235319297
> sage: N = IntegerModRing(euler_phi(n))
> sage: e = N.random_element()
> sage: while gcd(Integer(e), euler_phi(n)) != 1:
> ....: e = N.random_element()
> ....:
> sage: e
> 4548792647289896041320266443
> sage: gcd(Integer(e), euler_phi(n))
> 1
Yep, of course we need to check for some properties of e first.
> But from [1], we have
>
> sage: type(m)
> <type 'sage.rings.integer.Integer'>
>
> so Sage goes berserk here:
>
> sage: m^e
> ---------------------------------------------------------------------------
> RuntimeError Traceback (most recent call last)
>
> /home/mvngu/<ipython console> in <module>()
>
> /home/mvngu/usr/bin/sage-3.1.4/local/lib/python2.5/site-packages/sage/rings
>/integer.so in sage.rings.integer.Integer.__pow__
> (sage/rings/integer.c:9650)()
>
> RuntimeError: exponent must be at most 2147483647
>
> So in this case, it doesn't help to generate $e$ using [2].
I think it does if you then coerce the result to ZZ. One of the main features
of Sage IMHO is its object oriented approach i.e. that it is much more than a
calculator. If I was to write such an introduction I would like to introduce
this feature which makes working with many things much easier (i.e. having
rings one defines first etc.).
> > 7) for i in xrange(len(bin))
> >
> > that seems un-Pythonic to me. Why not do
> >
> > for b in b.digits() ?
>
> Yep, we can do that. However, note that
>
> sage: 2.digits()
> [0, 1]
> sage: list(Integer.binary(2))
> ['1', '0']
>
> so 2.digits() returns the binary digits of the integer 2 but the order
> of those digits are reversed. OK, this is more Pythonic:
>
> def modexp(a, b, n):
> d = 1
> for i in list(Integer.binary(b)):
> d = mod(d * d, n)
> if Integer(i) == 1:
> d = mod(d * a, n)
> return Integer(d)
Sage is in many areas little-endian friendly (smallest thingy comes first)
because this is how number theorist like it. You can always call the reversed
iterator on digits() though. However, this is really pedantic now and I'll
shut up :)
Martin
--
name: Martin Albrecht
_pgp: http://pgp.mit.edu:11371/pks/lookup?op=get&search=0x8EF0DC99
_www: http://www.informatik.uni-bremen.de/~malb
_jab: [EMAIL PROTECTED]
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-devel@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/sage-devel
URLs: http://www.sagemath.org
-~----------~----~----~----~------~----~------~--~---
