ToomCook multiplication for dummies
posted April 2014
We're learning a lot of algorithm in my algebre et calcul formel class. One of them is the ToomCook algorithm used for multiplication of large integers.
I found a super simple explanation of it on a forum, it helps:
2 commentsSay, we want to multiply 23 times 35.
We write,
p(x) = 2x + 3,
q(x) = 3x + 5.
We are using our realization that any integer can be written as a polynomial.
Here, p(x), represents 23, and q(x), represents 35, when x equals 10.
We write,
p(x)q(x) = r(x).
That is, p(x) times q(x), equals r(x).
So,
(2x + 3)(3x + 5) = ax^2 + bx + c = r(x).
Now,
p(0)q(0) = r(0).
So,
(20 + 3)(30 + 5) = a0 + b0 + c.
Therefore,
c = 15.
Now,
p(1)q(1) = r(1).
Therefore, when we do the substitutions (for x and c),
a + b = 25.
Now,
p(1)q(1) = r(1).
Therefore, when we do the substitutions (for x and c),
a  b = 13.
Now, we already know c, and we just need to find a and b.
We have two linear equations and two unknowns,
a + b = *25,
a  b = 13.
We just add the two equations and we get,
2a = 12.
Therefore,
a = 6.
Now, we can substitute 6 for a in,
a + b = 25,
and we get,
b = 19.
So,
r(x) = 6x^2 + 19x + 15.
Now, we substitute 10 for x in r(x), and we are done,
r(10) = 600 + 190 + 15 = 805.
Believe it or not!
Berlekamp & GO
posted April 2014
I knew that my principal cryptography professor Gilles Zémor was a GO player.
Which is pretty amazing in itself :)
But this keeps going on.
I have an algebra class this semester, and I'm trying to understand Berlekamp's algorithm. Trying to find videos on youtube about him I discover that he is as well a go player! And doing researches about the game at that! So cool :D
comment on this storyNAT Masquerade in one picture
posted April 2014
I wanted a recall on how masquerade worked in NAT, and I wanted a fast recall.
What's better than a picture? Nothing of course :D
comment on this storySlides with LaTeX
posted April 2014
If you read this blog, you know that recently I gave a talk on bitcoins.
I also gave a talk on whitebox cryptography last week.
One part of giving a talk that a lot of people tend to overlook is making good slides. I've always used Powerpoint for that, but for my last talk on whitebox cryptography I had two other persons on my team. Powerpoint was not an option if we were all working on the same file. LaTeX is the solution.
It's a real text file so you can use a revision control system like git, it's constant in its layout. You configure it at the beginning of the file and then you don't have to worry about it later.
We also had a fight (we were tired) on what theme to used. I went for no theme at all. Because everything else is visual noise.
Here's a great article from Zach Holman on the subject. If you ask me, and I'm not saying my slides are perfect, there are way too many crappy slides out there!
comment on this storyProcrastination
posted April 2014
Procrastination
I've read a LOT of stuff about procrastination. I have techniques:
 chaining
 get my ipod, put a 30 minutes timer and WORK nonstop until it rings
 Make lists
 Go to libraries
 Do sport
 In the morning, start by doing something productive right away
 Before sleeping, leave your work in the middle of something.
I think those are all my techniques, I can't really think of any others.
2 Ideas
A few months ago I started counting my calories intake, and I lost weight! It's magic. As soon as you start counting the bad stuff, you realize how much you're doing of it. I've had this idea for quite a long time, a slack counter, that times how long you slack per day. It compares that to the average. I don't know how to implement that, but a cellphone app would be the best suited I think. We always carry it, so we just have to launch the app and start a timer when we procrastinate. This + a firefox/chrome app that recognizes websites that are "time consumer" to add to your statistics. I'm sure that would help me work more!
When I'm really in trouble, and I can't seem to get motivated, I always take my iPod out and start a 30 minute timer. I do that, and then I find something to work on, anything, and I don't have to be efficient or know right away how I'm gonna work on it. I just have to do it, nonstop, to focus for just 30 minutes. And when the timer stops, I'm usually motivated enough to either keep going, or take a small break and start a bigger timer. I had the idea of implementing a 30 minute timer + a chain system, everyday you can start this 30 minute timer once and if you do work nonstop for 30 minutes while it runs, you will validate a day. Try validating the most days in a row!
Other techniques ?
This article brings 3 good points:
There are two ways to look at any task. You can do something because you see it as a way to end up better off than you are now – as an achievement or accomplishment. As in, if I complete this project successfully I will impress my boss, or if I work out regularly I will look amazing. Psychologists call this a promotion focus
when we say things like “I just can’t get out of bed early in the morning, “ or “I just can’t get myself to exercise,” what we really mean is that we can’t get ourselves to feel like doing these things.
Making an ifthen plan is more than just deciding what specific steps you need to take to complete a project – it’s also deciding where and when you will take them.
If it is 2pm, then I will stop what I’m doing and start work on the report Bob asked for.
You have to let go
This article helped/helps me a lot. Every time I fall into a procrastination period (because it's a disease you'll have to live with for the rest of your life :D), I read that article.
I hadn’t figured out the skill that would save me from the procrastination.
Until I learned about letting go.
Learn from the pro
Katia Verresen is a "Mental Energy coach" for CEOs and founders. Here's a nice article about her and interesting stuff she has to say about being efficient, in the zone.
Verresen is a big fan of a tactic called “calendar blocking,” and she encourages her clients to identify the chunks of time on their calendars when they have the most physical energy for work.
The mood you wake up in is critical. Consider it to be the default font for your entire day.
For a marathon runner, people say that the day before and the day before that are the most important. If you mess up with your sleep one day, you'll feel the consequences until two days after.
Verresen actually tells her clients that if they haven’t gotten enough sleep, they shouldn’t take their emotions seriously the next day.
“Mental energy is the ability to separate yourself from your thoughts,” Verresen says. “Everyday, we have millions of thoughts that cause stress, anxiety, depression — that can stall you out in a million different ways — but you don’t have to believe them.”
“The best way to reset your mental energy is to get it up and out into the physical world,” Verresen says. “Screens don’t count. You should put whatever it is that’s bothering you or that you need to get done up on a white board. Write it down and stick it up on a wall.
I sometime stop what I'm doing to do the dishes. It clears my mind.
Verresen advises her clients to block off two slots ranging between 90 minutes to 2 hours every week as mental white space. They need to literally put it on their calendar and make sure they aren’t interrupted or disturbed during this time — ideally they shouldn’t have meetings right afterwards either.
I do this by doing my laundry. I take a paper and a pen with me and I go do my laundry for an hour.
comment on this storyGröbner basis on numb3rs
posted April 2014
It doesn't seem to be the only appearance of the Gröbner basis on the show:
In the Season 4 opening episode 'Trust Metric' (2007) of the television crime drama NUMB3RS, math genius Charlie Eppes mentions that he used Gröbner bases in an attempt to derive an equation describing friendship.
From wolfram alpha
comment on this storyAn awesome explanation of the Fourier Transform
posted April 2014
I've run into this über cool explanation of the Fourier Transform thanks to mtodd's blog
Here's a bit from the introduction:
What does the Fourier Transform do? Given a smoothie, it finds the recipe.
How? Run the smoothie through filters to extract each ingredient.
Why? Recipes are easier to analyze, compare, and modify than the smoothie itself.
How do we get the smoothie back? Blend the ingredients.
And cool examples of what can be done with the Fourier Transform:
comment on this story
 If earthquake vibrations can be separated into "ingredients" (vibrations of different speeds & strengths), buildings can be designed to avoid interacting with the strongest ones.
 If sound waves can be separated into ingredients (bass and treble frequencies), we can boost the parts we care about, and hide the ones we don't. The crackle of random noise can be removed. Maybe similar "sound recipes" can be compared (music recognition services compare recipes, not the raw audio clips).
 If computer data can be represented with oscillating patterns, perhaps the leastimportant ones can be ignored. This "lossy compression" can drastically shrink file sizes (and why JPEG and MP3 files are much smaller than raw .bmp or .wav files).
 If a radio wave is our signal, we can use filters to listen to a particular channel. In the smoothie world, imagine each person paid attention to a different ingredient: Adam looks for apples, Bob looks for bananas, and Charlie gets cauliflower (sorry bud).
DiffieHellman, ElGamal and RSA
posted April 2014
I'm in holidays for a week, easter I think, anyway, I didn't know what to do so I coded the DiffieHellman handshake, the ElGamal cryptosystem and the RSA cryptosystem in python.
You can check the code on github here: github.com/mimoo/crypto_studies
Check the tests.py
file to see how the classes are used. Here's an extract:
"""Testing Diffie Hellman
"""
# 1. BOB
bob = DiffieHellman()
# G and g are generated automatically
print("G is a group mod %i and of order %i, and the generator g is %i" % (bob.G[0], bob.G[1], bob.g))
# We generate a secret and a public key
bob.generate_secret()
bob.generate_public()
# 2. ALICE
# We already know G and g
alice = DiffieHellman(bob.G, bob.g)
# We generate the secret key and the public key
alice.generate_secret()
alice.generate_public()
# 3. WE CREATE THE SHARED KEY
bob.generate_sharedkey(alice.publickey)
alice.generate_sharedkey(bob.publickey)
# Bob and Alice now have the same _sharedkey and the same public (G, g)
As the README
says, it might be oversimplified and not totally correct. I mostly did that to do something in Python and also try to memorize how those systems work.
I've also done a lot of Unity this weekend. And also a bit of WxPython but I don't really like it. I think I should focus on QT and C++.
comment on this storyWhitebox Cryptography
posted April 2014
Those past few months I've been working on a C implementation of a whitebox using Chow et al's paper and the DES algorithm.
It's not done yet but the code is available on github. I also did a C implementation of DES just to get a grip on it, it's available on github as well.
I just did a presentation of the research my team and I did, I think it went pretty well. The slides are here
comment on this storyHow hard is it to find an internship?
posted April 2014
I've been looking for a summer internship and I haven't really found anything sor far. Although I've had some interviews with some start ups from the Silicon Valley (including TrueVault that really seemed like a good fit for a cryptographer in progress like me :D). But I've been unlucky so far since they're pretty busy, it's demo daytime for those applying to ycombinator there.
Anyway I still have 4 months of holidays this summer and I'm wondering what I'll do if I can't find anything in Mountain View (n_n I really want to go there).
If you know someone, or are interested in a passionate coder and eager learner, you can take a look at my resume here and rush to contact me before someone else does :)
Otherwise I'll spend more time coding personal projects and writing this summer (by the way, Korben, a famous influential blogger in France has written about me and my application 3pages.fr in a blog post. Huge amount of traffic in a few hours, 600 people signing up in a day. I envy his traffic.)
comment on this storyNAT with iptables : super fast tutorial
posted April 2014
So I know how to use iptables, I know what a NAT is, but I don't want to learn how to exactly do it. Misery... I have to learn how to do it because I have an exam that will probably ask me how to do it in a few days. So I've been looking for a super simple tutorial, a 1 minute tutorial, on how to setup a NAT configuration with iptables in 1 minute. Couldn't really find it so here it is, if this is somewhat useful for someone, you're welcome.
First Step
For NAT to work, you have to allow forwarding on your server. Easy peasy:
$ echo 1 > /proc/sys/net/ipv4/ip_forward
Also, before adding new iptables rules, be sure to check what rules you already have
$ iptables L
you should allow some forwarding for it to work (if the policy is default to DROP). But this not a tutorial about iptables.
Static
I have a server with:

eth0 connected to the network
 eth1 connected to internet
Let's modify the PREROUTING part. Traffic coming from internet on our public address (@pub) and trying to reach our machine:
$ iptables t nat A PREROUTING d @pub i eth0 j DNAT todestination @priv
Let's modify the table nat, append a rule to the pretrouting section : something is trying to reach @pub ? Let's put it in our input interface eth0, jump to the Destination Nat protocol, which tells us to send the packet to @priv.
Now Let's modify the POSTROUTING part. Traffic coming from inside our network and trying to reach something, somewhere on internet:
$ iptables t nat A POSTROUTING s @priv o eth1 j SNAT tosource @pub
If the packet is coming from @priv, let's put it on our output interface eth1 and jump to the Source Nat Protocol that will modify the packet so it has the public address (@pub) as source.
Here! You did it. One private IP address mapped to one public IP address.
Dynamic
Same kind of configuration but now we have several private addresses and only one public address.
$ iptables t nat A POSTROUTING s @priv/mask j MASQUERADE
We can modify every packets coming from the subnetwork @priv to get masqueraded.
$ iptables t nat A POSTROUTING o eth1 j MASQUERADE
Or we can just tell all the network to get masqueraded.
And this is it. No PREROUTING Needed.
Again, you're welcome ;)
2 commentsExams
posted April 2014
We've been a group of 45 students spending each nights at the Crémi these few last days, this building of three floors where each floor has around 10 rooms full of computers.
We work, we eat, we play, and we crash each other computers.
There are a bunch of games installed on every computers but we mostly play SauerBraten, a quakelike.
My 15yearold self would have spent most of his days here playing, if only he knew that his future campus would have such a sacred place :)
How do we crash each other computer? We just ssh into their machine and launch a fork bomb:
:(){ ::& };:
comment on this storyIt operates by defining a function called ':', which calls itself twice, once in the foreground and once in the background.
Fast Fourier Transform
posted April 2014
So, I've learned about Fourier every year in my bachelor of Mathematics and I'm learning about the efficient algorithm dealing with the Fourier Transform in my class of Algebra right now.
I found a really nice video explaining really quick what it is, concretely.
Here's wikipedia way of showing that made by LucasVB, this crazy guy doing all those math gifs you've probably seen before :) more here
There's also a visualization in d3.js here: http://bl.ocks.org/jinroh/7524988
comment on this storyTrue randomness... exists?
posted April 2014
A great article from AskAmathematician about true randomness.
The question is actually geared towards physicists and the tl;dr is: true randomness exists. Take that causality believers.
And as I expected, the experience to prove this is done with photons:
http://www.askamathematician.com/2009/12/qdophysicistsreallybelieveintruerandomness/
comment on this story