Stage de M2 – Protocoles d'échange de clefs à base d'isogénies
October 31, 2016
Une isogénie est un morphisme surjectif et de noyau fini de variétés
abéliennes. Les exemples les plus simples d’isogénies sont les
morphismes algébriques de courbes elliptiques qui préservent les
points à l’infini.
La cryptographie à base d’isogénies est une des branches les plus
jeunes de la cryptographie asymétrique. Initiée il y a seulement 10
ans par les travaux sur les réductions de logarithmes
discret , et sur les fonctions de hachage prouvablement
sûres, elle s’est ensuite enrichie de protocoles d’échange de
clef . Il existe essentiellement deux protocoles d’échange
de clefs à base d’isogénies : un basé sur les courbes elliptiques
ordinaires, et un autre basé sur les courbes elliptiques
supersingulières. Ces deux protocoles ont tous les deux
l’intérêt de résister à des cryptanalyses par ordinateur quantique
(algorithme de Shor), mais seulement le deuxième est considéré
suffisamment efficace pour être utilisable en pratique.
Toutes les constructions cryptographiques à base d’isogénies reposent
sur des problèmes de recherche de chemins dans des graphes
d’isogénies ; ce sont des (multi)-graphes non-orientés où les sommets
sont des variétés abéliennes à isomorphisme près, et les arêtes sont
La structure des graphes d’isogénies est régie par celle des anneaux
d’endomorphismes des variétés abéliennes. Dans le cas des courbes
elliptiques ordinaires, la théorie de la multiplication complexe
lie les isogénies aux idéaux fractionnaires d’un corps de nombres
quadratique imaginaire . Dans le cas des courbes elliptiques
supersingulières, ce sont les idéaux à gauche des ordres maximaux
d’une algèbre de quaternions qui jouent le même rôle . Ces
théories se généralisent aux variétés abéliennes de dimension
supérieure , mais elles ne sont pas aussi complètes
que pour le cas elliptique.
Sujet du stage
Le but du stage est d’étudier le protocole d’échange de clefs de
Rostovtsev et Stolbunov, d’en proposer une variante efficace, et
d’en estimer soigneusement les paramètres de sécurité par une étude
des attaques quantiques connues.
On cherchera des pistes pour améliorer le protocole dans les
techniques utilisées dans les protocoles à base d’isogénies
supersingulières, ainsi que dans les généralisations aux dimensions
supérieures. L’analyse de sécurité se fera en tenant compte des
modèles de sécurité en cryptographie classique, ainsi qu’en
En cas de succès, le stage pourra se poursuivre naturellement par une
thèse en cryptographie à base de courbes elliptiques et isogénies :
construction de nouveaux cryptosystèmes, cryptanalyse, calcul
d’anneaux d’endomorphismes, etc.
Connaissances mathématiques en algèbre, théorie des nombres et
géométrie (corps finis, corps de nombres, courbes elliptiques, …).
Connaissances en algorithmique (par ex.: grands entiers,
factorisation, primalité, arithmétique des courbes elliptiques).
Maîtrise d’un système de calcul formel (par ex., SageMath, Pari/GP,
Connaissance d’un langage de programmation.
Aucune connaissance en calcul quantique n’est requise, mais ceci peut
être un plus.
Le stage s’effectuera dans l’équipe
GRACE de l’Inria Saclay, sous la
direction de Luca De Feo et de
Le stagiaire sera amené à interagir avec le Laboratoire Cryptographie
et Composants de l’ANSSI.
Pour candidater, envoyez un email à firstname.lastname@example.org en joignant votre
CV et une lettre de motivation.
8 weeks and 60 students with Cloud9
June 11, 2014
I would like to finish my series on teaching web programming with a
report on how the online IDE Cloud9 helped improve my
As you might know if you
read French newspapers,
UVSQ is a university on a low budget. The department has only one
computer room, and it is best avoided. Students bring their own
laptops to tutorials, or they can borrow one from the library.
When I gave my course the first year, several precious tutoring hours
were lost installing, configuring and debugging WAMPs, LAMPs and
virtual machines. The switch to Node.js eased
things up: installation was generally smooth, apart for some version
problems on Ubuntu machines and missing SQLite interfaces for
Windows. Both years, I had to teach the students, especially those not
on Linux, how to launch and use a terminal.
Having decided to go back to PHP, I absolutely wanted to avoid the
painful installation of Apache and stacks. The cloud IDE Cloud9 looked
like a promising alternative, lifting the burden of handling dozens of
Cloud9 is a commercial product, offering free unlimited workspaces for
public development, plus one private workspace. It has some
integration with GitHub, BitBucket and Heroku, and some limited
history and collaboration features are also available for free
accounts. It can natively execute and debug Node.js instances, or run
PHP applications via Apache (other runtimes are also supported). It
includes a MySQL and a MongoDB server for development.
Thanks to Cloud9, the only problems left to solve on the first
tutorial were laptops not connecting to the network, and students
having confirmation emails from Cloud9 delayed or blocked by their
Once they were connected to the Cloud9 dashboard, the students could
get started coding immediately by cloning the
project skeleton I had hosted
for them on GitHub. From then on they could work on their project (no
knowledge of git required), while I could update their configuration
files by asking them to pull. Some students eventually managed to mess
with their local git clone, but fixing it was a minor annoyance
Previewing static html files and running apps is as easy as a button
click: all students quickly caught the workflow, although some of them
were slow to grasp the difference between viewing static files and
Because all projects are public, I could connect to the students’
workspaces at any time and observe their work live. This was useful in
the classroom, but even more important when addressing help requests
out of the class. The embedded chat room was also very useful when
helping students from home. Beyond the IDE front-end, each workspace
also offers a publicly accessible webdav directory. This let me easily
crawl and download all the students’ work for local examination and
grading. I found this very convenient for the first part of the
course, where only client code was involved. At least in one case, my
local copy also served as a back-up save for a student who had
accidentally erased all her work.
However, visitors to workspaces do not have the rights to run
processes, hence they cannot run server code. When the students
started writing server code and using SQL, reproducing their
environment locally turned out to be too painful. Thus, I had to
resort to asking them for write permissions on their workspaces, which
also turned out to be a very convenient way to help them fixing Cloud9
glitches from a distance. In retrospect, I should have asked write
permissions from the beginning.
Finally, some comments on cheating. Yes, any student could see any
other student’s work, if he could guess his colleague’s login and
workspace name. This is in my opinion very good, and most students
used it constructively: taking example from their comrades’ code,
using the chat to help each other, and even collaborating on
code. Obviously some students didn’t refrain from using it to cheat,
and some went even as far as creating Cloud9 accounts with logins
similar to mine, so to not awake suspicions in their comrades. In
reaction, some of the good students created accounts with unguessable
usernames, or used the one free private project.
However it wasn’t too hard to unmask the cheaters. My own
plagiarism detection scripts
helped me narrow down the hunt, Cloud9 history tool did the rest: by
rewinding history, I could easily know when the students had been
working, when the copy-paste had happened, and what variables had been
renamed. Not only I had a very easy time detecting cheating, but I
even had irrefutable proofs of it.
Cloud9 wasn’t all joys and wonders. For one, it requires a good
network connection to function properly. Wifi connections, such as
eduroam, are likely to give a horrible experience. As obvious as this
may sound, some students kept forgetting or refusing to bring ethernet
cables: I had to always bring a stock with me.
Even on a wired connection, though, most students experienced serious
problems. The IDE would often lock one file or freeze completely, the
only solution being reloading. Before I prompted the students to
enable auto-saving, network errors would occasionally destroy one hour
worth of work. After they enabled auto-saving, some students
experienced severe slow-downs of the interface, and even then some
work was occasionally lost. Sometimes, after recovering from a freeze,
some files would be empty; a peak at the history would usually yield
all the contents back, but restoring previous versions is horribly
clumsy in the free version of Cloud9.
About a dozen of workspaces got locked at some point, with the
interface simply not able to read the filesystem. This required the
intervention of Cloud9 staff, often holding the student from working
for the rest of the day. In March, we were also unlucky enough to
experience a major platform problem affecting POST requests right
before a submission deadline.
Overall the use of Cloud9 turned out to be very frustrating for some
students. I wonder if the time gained by not having to install
anything locally wasn’t compensated by the time lost fighting Cloud9
glitches. Thankfully, Cloud9 staff was very kind and responsive, and
usually solved all problems in one day’s time.
To my surprise, more than 50% of the students thought very well of
Cloud9, grading it 4/5 or 5/5. In the end, I think the experiment
turned out well, and, whatever platform I am going to use next year,
there is no going back to the dear old local install. Beyond being
stable and not loosing data, my ideal platform would:
- Use Cloud9 IDE as front-end, or similar.
- Let me manage my group of students, view their projects, and
automatically grant me write privileges on their repositories.
- Keep history robustly and often (e.g., using auto-save and Git).
- Do not allow the students to create multiple logins, and force them
to be connected in order to use the platform.
- Simplify some workflows (e.g., using the MySQL database).
- Redirect PHP logs to the IDE console.
Maybe this can be achieved by installing the open source version of
Cloud9 on a university server with a customized back-end. I will
likely be experimenting with this before next year’s course.
For reference, I report here some non-trivial configuration details
and bug fixes that I had to apply during the course.
Due to bugs in Cloud9, or to bugs in the students code, the
interface may freeze repeatedly. While it is not guaranteed to work, adding
?reset=1 to the workspace URL may help fixing problems. It simply
returns the workspace to its initial state: no files open, no
previews, no applications running. Here’s one funny case where this
and opened its web page in the “Preview” tab. The preview would
freeze the whole interface and crash the browser tab. But at each
reload Cloud9 would open again the “Preview” tab… and crash again!
php.ini file is placed in a Cloud9 workspace, its settings
supersede the global ones. This has various uses: activate sessions,
printing errors, etc. One important use for Silex: the PHP package
manager Composer wants the setting
date.timezone to be set.
Integration with PHPMyAdmin is sure in the plans for Cloud9, but not
ready yet. The simplest solution for me was to ship a lightweight
open source MySQL manager, SqlBuddy,
together with the project skeleton.
One of the most annoying bugs, happening almost systematically,
prevents the MySQL server from starting after a workspace
freeze. This is a known bug with a fix documented
but, had I known it before, it would not have hold so many students
for the entire tutorial following spring break (during which many
Finally, one of the most random problems was caused by GitHub. The
students working with Silex had to install it in Cloud9, together
with its dependencies. I had given a
composer.json file, so that
they just had to run Composer in the Cloud9 terminal in order to
download and install everything. Composer connects to GitHub’s API,
and GitHub limits anonymous requests to 60 per hour per IP. Since
every user in Cloud9 has the same IP, chances are that some student
may get rate limited. Fortunately Composer will fail with a
meaningful error message, and will ask for a GitHub login in order
to solve the problem. Unfortunately, the average student will not
have a GitHub account, and will not understand what the message is
asking for, so if this happens outside the class, expect an email. I
was lucky: this happened only once. Another fix is described
8 weeks, 60 students and 1 web application
June 10, 2014
To continue my series of posts on teaching web programming, I would
like to share on the project students had to realize for my
web programming course.
In past years, I used to ask the students to develop a web application
of their likes, setting some minimum requirements to pass the
course. I picked this from beginner courses I had been tutoring for in
and in Paris VII, while I was a PhD student.
Although this formula was very successful in École Polytechnique, and
reasonably good in Paris VII, it was very disappointing in my own
course. I got tired of having to grade, over and over, the usual forum
application, mostly grabbed off the Internet and poorly put
together. Some of the best projects sure were able to blow my mind,
like a fully functional battleship game, or an almost functional
But the large majority of it was just dull and boring, when it wasn’t
I think the reasons for this failure sum up to: student level highly
inhomogenous, course requirements too high for most students, course
duration too short. Mostly the opposite of what we had in
Polytechnique and Paris VII. I was not ready to give up on the
requirements, so I had to find a way to force the students to keep up
with the course and do more work.
The directed project, to be developed during the tutoring sessions (3
class hours per week, plus a lot of homework for most students),
turned out to work very good. It was rather ambitious: write a
application. I have to admit it even flirted with the impossible: the
last part required to push play events from the server to the clients;
something very natural to code in Node.js, but very unnatural in
The progression kept the students interested all along. They strove to
complete all the requirements, going well beyond what they would have
achieved on a project of their own. Almost everyone got to write some
AJAX interaction: something I had not even dreamed of in past years. I
was amazed to see several students complete all the requirements,
fully functional Connect-four game.
According to the polls, 80% of the students found that the course
required more work than other masters’ courses, but they got
relatively high grades, and 75% of them where happy about it. But
didn’t this make cheating worse? Quite the contrary, as I will develop
in the next post.
One thing some students complained about was the lack of feedback on
the quality of the work they were providing. I collected and graded
their work twice (once mid-course, once at the end), was several weeks
late giving grades, and could hardly have done more, given that I was
alone grading 60 students. Also, just two numbers hardly give much
information on what’s good and what’s bad in the code.
Auto-graders could provide one way of improving feedback. In the
future, I think it would be interesting to experiment with them,
although I am afraid they could hinder the students’ creativity by not
inspiring them to freely explore. Another interesting way in which
auto-graders could complement the directed project would be to isolate
and teach fundamental concepts by short, self-contained exercises
focusing on specific skills (e.g.: navigating the DOM, building a HTTP
response by hand, etc.).
Given that the course already has a good deal of video material, and
that I am planning more of it for next year, the use of auto-graders
would make it more and more akin to a MOOC. Who knows…
8 weeks and 60 students with Silex
June 5, 2014
From February to May, I have taught my usual eight weeks
web programming course at Université de
Versailles. The course, called Applications Web et Sécurité (Web
Applications and Security) is aimed at first year masters’ students
with a computer science major. This is the third time I have taught
this course, and for the third time I have messed up with most of the
syllabus in search of the magic formula. I haven’t found it yet, but I
think I got a bit closer.
This year’s course was different from the previous ones in many
- Class material was written in French.
- Tutorials were structured so to construct a full web application
from the ground up. The design was mostly given in the syllabus. All
students had to implement the same application, individually or in
pairs. I would give marks to the final product, which would account
for one third of the course grade.
- Students had the choice to develop the application in
- All development was done in the cloud, using the online IDE
I am going to share my experience in a series of blog posts, hoping to
spark some thoughts/reactions/new ideas among my colleagues teaching
similar subjects. I will start by discussing the technologies I chose.
The first year I gave this course, I taught standard PHP+MySQL over a
WAMP, LAMP or MAMP stack; a common choice for this kind of course,
also inherited from my previous experiences. The course was a big
Unfortunately, I hate PHP. The next year, I switched to native Node.js
(no Express), with
Mustache and SQLite/MySQL. Along the
way, I wrote a
micro-framework to guide
the students in their development. The course was a disaster. Almost
half of the students dropped the course midway. Of those who stayed,
most could not grasp the basic concepts behind Node.js. I ended up
receiving dozens of version of the classic chat room on web sockets
app: I had not taught web sockets, but chat rooms were basically the
only examples written in Node.js one could find on the Internet at the
Why was it so hard? The answer is: “basics”. Most of the students could
not grasp the concept of callback, let alone event-driven design!
Also, Node.js was not as popular as it is now: most students were
expecting a PHP course (two thirds of the students already know some
PHP), also in consideration of their employment
perspectives. Fortunately, the usual handful of very good students was
there to cheer me up.
So this year I had to go back to more familiar grounds, but I didn’t
want to loose the work done with Node, and still wanted to keep some
of the clean separation of concerns achieved by it. I first thought of
Symfony: a very elegant PHP framework, open
source, developed in France, and enjoying high demand from the
industry. However, Symfony is a mastodon, with too much magic
happening under the covers. By reading more about Symfony, I
discovered Silex, a PHP
micro-framework developed by the same company as Symfony, open source,
remarkably similar to Node.
The match was perfect, I can even say Silex reconciled me with
PHP. All the concepts I wanted to teach exist almost identically in
Silex and Node (with Express, this time): HTTP, routers, views,
template languages (Twig was a natural
choice), DBALs, AJAX, REST APIs, Server push, security, … I could
lecture on the theoretical principles giving examples both in PHP and
Node, while the tutorials would have to be specialized for each
language. This required a little more work on the tutorials, but
nothing very serious (especially when compared with the huge amount of
work the rest of the course gave me). I made very clear from the
beginning that Node.js is for the good students, and that the
official framework for the course is Silex. This had the perverse
effect of pushing even some of the best students towards Silex (only 4
of 60 students chose Node), but I am confident that those ones will go
back and have a look at Node anyway.
The cleanliness and lightness of the micro-frameworks made it possible
to focus on fundamental low level details, and most importantly did
not impose a specific pattern, such as MVC. Lecturing with two
languages helped the students visualize the separation between coding
patterns and actual technology.
I was afraid that students with a background in PHP would be reluctant
to change their coding habits and learn how to use a modern framework
and a template language. However this turned out to be a minor
problem: it was enough to clearly state once or twice that they had to
forget everything they knew about PHP. Most of the students, beginners
and not, understood the added value of those modern tools on their
employability, and happily followed the dense syllabus and adhered to
To conclude, I am really happy with the two technologies I chose and
with the style of lecturing this implied. What’s most important, the
students where happy too. At this stage, it does not seem implausible
that I may add a third framework to the course someday (Python with
Flask comes to the mind).
The Website Opens
June 28, 2013
The new website is opening today!
It is still under heavy development, but you can already enjoy its
basic features. The blog is not completely functional yet, come back