2008/11/5 Minh Nguyen <[EMAIL PROTECTED]>:
>
> 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.
Actually since 3.2.alpha1 the Integer parameter is no longer there in
gcd() and lcm() (see #3118).
John
>
>
>> 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
-~----------~----~----~----~------~----~------~--~---
