Hi Martin,
Martin Albrecht wrote:
>> http://nguyenminh2.googlepages.com/sage_numtheory-crypto.pdf
>>
>> This is a short tutorial on using Sage to study elementary number
>> theory and the RSA public key cryptosystem. By "short", I mean at most
>> 10 pages. If anyone has write privileges on the www.sagemath.org
>> server, you're welcome to put the above PDF document there or
>> somewhere where folks can access them. Hope (new) users find the
>> tutorial helpful in getting themselves familiar with Sage.
>
> Hi Minh,
>
> I have a few remarks about your nice introduction. I'm not sure whether you
> accept criticism/suggestions, but I figured I send them in any case:
>
> 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. 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"
> 2) "The command gcd has an optional argument called integer, which defaults
> to
> the value of False."
>
> It might be worth pointing out that this flag has no effect on the result
> that
> is returned.
Yep, you're right. Tutorial's updated.
> Also note to self: the flag seems odd to me, why don't we just
> check types?
>
> 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".
> 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.
> 5) the pseudocode on top of page 8
>
> sage: m = list("HELLOWORLD")
> sage: S = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
> sage: for i in xrange(len(m)):
> for j in xrange(len(S)):
> if m[i] == S[j]:
> m[i] = j + 65
>
> can be done more python-ic like this:
>
> sage: m = "HELLOWORLD" # no need for list()
> sage: m = [ord(c) for c in m]
> Also, you can convert to an integer like this:
>
> sage: ZZ(list(reversed(m)),100)
> 72697676798779827668
Yep, list comprehension and friends are nice features of Python, and I
really like them. But I don't want to assume that Sage beginners are
familiar with those features. Of course, the pseudocode can be
re-written like this:
[1]
sage: m = "HELLOWORLD"
sage: m = [ord(c) for c in m] ; m
[72, 69, 76, 76, 79, 87, 79, 82, 76, 68]
sage: m = ZZ(list(reversed(m)), 100) ; m
72697676798779827668
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.
> 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.
> 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
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].
> 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)
> I hope you find my comments helpful.
I greatly appreciate all your comments and suggestions. The tutorial has
been updated to reflect many of your suggestions. Here it is, hot off
the digital press:
http://nguyenminh2.googlepages.com/sage_numtheory-crypto-v2.pdf
--
Regards
Minh Van Nguyen
Web: http://nguyenminh2.googlepages.com
Blog: http://mvngu.wordpress.com
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
