I’ve recently taken an online course on cryptography, which is taught on Coursera by Dan Boneh, Professor of CS and EE at Stanford University. I can’t praise the course enough for its thoroughness and reasoning about pretty much everything you’d want to know about cryptography and I strongly advise anyone interested to give it a try.
Programming assignments are one of the particular features of the course. Even though they are not required to obtain a certificate, they still are fun and challenging exercises, strengthening your grasp of cryptography theory. The choice of how exactly you will complete assignments is up to you, any programming language or style is fine. This post is for those who prefer using Ruby for just about anything.
As part of your implementation, you are required to manipulate very large numbers in some peculiar ways, and instead of seeking help from Ruby native citizens like Bignum or BigDecimal, my suggestion is to use the blazing fast C library GMP and GMP RubyGem which provides Ruby bindings to GMP.
Make sure you have Ruby, RubyGems and GMP library installed and working.
Install the gem:
$ gem install gmp
Include GMP into the namespace:
require 'gmp'
include GMP
Use your superpowers wisely.
Start by creating a GMP-flavored integer:
a = Z(93) # => 93
a.class # => GMP::Z
\(x = \lfloor\sqrt{a}\rfloor\)
x = a.sqrt
\(x = a^c\)
x = a**c
\(x = \gcd(a, b)\)
x = a.gcd(b)
Extended Euclidean algorithm: \(x = \gcd(a, b)\) and \((m, n)\) are Bézout coefficients for \((a, b)\) such that \(a m + b n = \gcd(a, b)\)
x, m, n = a.gcdext(b)
\(x \equiv a^{-1}\pmod{p}\) such that \(a x \equiv a a^{-1} \equiv 1\pmod{p}\)
x = a.invert(p)
\(x \equiv a^c\pmod{p}\)
x = a.powmod(c, p)
require 'gmp'
include GMP
Z(10).sqrt # => 3
Z(7).invert(17) # => 5
Z(5).powmod(5, 7) # => 3
((Z(93)**94)**95)**96 # => really large number computed very fast
You will not find them here.
comments powered by Disqus