Till KTH:s startsida Till KTH:s startsida

Gruppwebben som samarbetsyta stängs 1 oktober 2026. Du som administratör behöver nu exportera gruppens innehåll och/eller radera gruppen.

Observera: Från och med den 1 oktober 2026 kommer delar av gruppwebben som inte längre används, successivt att stängas ned, exempelvis gruppwebbar som redan har flyttats eller varit inaktiva under en längre tid.

Mer information hittar du i nyheten: Gruppwebben och Social stänger den 1 oktober 2026. Stöd och instruktioner för hur du exporterar en gruppwebb finns i: Gruppwebben som samarbetsyta stängs 1 oktober 2026..

Handouts

All handouts in the course will be available here.

General Information

Douglas Wikström skapade sidan 1 januari 2016

kommenterade 19 februari 2016

In question 7 of homework 1, can we assume that "Hoffman" is a typo and should be read "Huffman"?

Anmäl missbruk
kommenterade 23 februari 2016

Hi! I don't seem to have received files for HW1 problem 1. I sent an email to you last friday per the instructions in the HW1 pdf, but I'm not sure if it got delivered properly. I sent another one just now, just in case. I haven't had any issues with sending email from the kth.se address before, so please check whether you've received any of the emails. Thanks.

Anmäl missbruk
kommenterade 23 februari 2016

Is there a typo in problem 6c?
We input a 128-bit random variable into a function on 256-bit inputs.

Anmäl missbruk
Lärare kommenterade 23 februari 2016

No, but information is missing. You can set the top 128 bits to zero.

Thank you for pointing this out to everybody!

Anmäl missbruk
kommenterade 23 februari 2016

Problem 9 clarification: We assume n is even for the Feistel network, right?

Anmäl missbruk
kommenterade 23 februari 2016

Is there a typo in problem 6e?

Y is an (n+1)-tuple, but said to be a random variable over {0,1}^n, i.e. a set of n-tuples.

Anmäl missbruk
Lärare kommenterade 23 februari 2016

Yes, n is always even in a Feistel network.

Anmäl missbruk
Lärare kommenterade 23 februari 2016

Problem 6(e): You may think of Y either way, since Pr[X_0=1]=1.

Anmäl missbruk
kommenterade 27 februari 2016

Do we get some implementation points if we manage to go through all test cases on Kattis but the last (time limit exceeded) for the AES part?

Anmäl missbruk
Lärare kommenterade 28 februari 2016

I am sorry, but the answer is no. I do not have the resources to go through the solutions of the students and figure out which are good partial solutions.

I need to rely on Kattis for checking that you implemented AES correctly and then I can quickly browse your code during the oral exam to see that you write decent code and understand your own code.

Writing fast enough code is part of the problem and an important part of a course like this, so you need to think about what you do in your code and/or profile it.

A crude way to profile code like this is to comment out some lines and see what happens with the running time. A better way is of course to use a profiler.

Doug

Anmäl missbruk
kommenterade 1 mars 2016

Hi, I have a question regarding the input argument in Kattis. Is it a file which contains the key and the plaintext, or is it a sequence of numbers (in binary or hexadecimal representation)?

I would appreciate an example with the same format of the call that is made to test the program, as I have not used Kattis before.

Thank you!

Anmäl missbruk
kommenterade 1 mars 2016

There is an example file which is exactly what you get through the standard input in Kattis on the description of the problem. The bytes are directly written as is, which means that when you open the example file with a text editor you just get gibberish that depends on your default encoding as your computer tries to interpret the bytes as characters.

Anmäl missbruk
kommenterade 1 mars 2016

Yes I know that, but my question is if the input is actually a file like that example or just that bit string in hexadecimal/binary. I mean, how the call looks like:

(compiler) input_file program

(compiler) 01101010101011... program

(compiler) D40193.... program


Where input_file is like the example file. Thank you for your answer!

Anmäl missbruk
kommenterade 1 mars 2016

Second option: you get a bit stream through standard input.

Anmäl missbruk
kommenterade 3 mars 2016
Regarding question 5, do we need to insert the code into the report or is it fine if it's just uploaded and accepted on Kattis?
Anmäl missbruk
kommenterade 3 mars 2016

I also have some problems with the AES input/output:

My code works fine with the provided test cases on kattis:
$ ./a.out < aes_sample.in | diff aes_sample.out - && echo "success"
success

But it gets a "runtime error" on kattis. I first thought that it was something with handling multiple blocks for encrypt so I made a testfile that has the same key as the provided example and then the plaintext block repeats 3 times:
$ hexdump aes_3.in
0000000 c0f4 a020 f6a1 fd04 3f34 6aac 6a7e f9e0
0000010 95f2 31b9 998b 3444 3dd9 a498 49e4 d8af
*
0000040

This works also fine with my program:
$ ./a.out < aes_3.in > aes_3.out
$ hexdump aes_3.out
0000000 e452 cb18 beb1 4949 8b30 1638 b191 fe09
*
0000030

The only exits I make in my program happen when I can't read 16 bytes. Here is my basic input/output logic:
int main() {
  FILE *s_in, *s_out; // stdin stdout
  s_in = freopen(
    NULL,
    "rb", // read binary
    stdin
  );
  s_out = freopen(
    NULL,
    "wb", // read binary
    stdout
  );
  if(!s_in || !s_out)
    exit(EXIT_FAILURE);
  r = fread(key, 1, 16, s_in);
  if(r != 16)
    exit(EXIT_FAILURE);
  while(fread(block, 1, 16, s_in) == 16) {
    // encrypt the block
    fwrite(block, 1, 16, s_out);
  }
  return EXIT_SUCCESS;
}

Can someone please point me in the right direction? Thank you :)

Anmäl missbruk
kommenterade 4 mars 2016
For the ciphertexts, can we make it more readable in the paper solution by replacing "_" and #" by their respective interpretations?
Anmäl missbruk
kommenterade 4 mars 2016

I solved my input/output problem: it seems like that freopen() doesn't work on kattis. Using stdin/stdout without explicitly setting them to binary mode works fine :-)

Anmäl missbruk
En användare har tagit bort sin kommentar
Lärare kommenterade 4 mars 2016

Please do not ask questions like that of Raees above. You need to think about it yourself and simply read the problem statement carefully.

Anmäl missbruk
Lärare kommenterade 4 mars 2016

On the other hand, in the recent news flash I opened the door completely for you all to share how to read and write to Kattis.

DO NOT SHARE ANY AES CODE!

Anmäl missbruk
kommenterade 5 mars 2016

About that^ . Can anyone tell me why what Kattis is doing is different to running:

python aes.py < aes_example.in

Because on Kattis trying to do sys.stdin.read() is throwing an exception and I don't know which.

Anmäl missbruk
kommenterade 5 mars 2016

For those struggling with IO on Kattis here's some code in C.

Click here for a pastie with some C code reading and writing binary input/output: 

As always with C, consult the man pages if you want to learn more.

Type "man fread" into a terminal for information about fread and fwrite. Otherwise click here for man pages for stdio.h. 

Anmäl missbruk
kommenterade 5 mars 2016

Hi, 

Can someone help me formatting the output in C++?

I am currently using "std::cout << myCipherText" to return the output but Kattis answers with a "Wrong Answer". My program encrypts every block perfectly, as I have compared the result with an encryption online tool, so my problem is in the formatting of the output. I have been trying this all day so I will appreciate if someone could help me for this. After moving from Python to C++, because of performance issues, it would be awful not to submit successfully this assignment because of the formatting of the data.

Thank you very much,

Anmäl missbruk
kommenterade 5 mars 2016

Alfonso, you can use putchar() to write chars to stdout. It worked for me, but maybe there is a better way.

Anmäl missbruk
kommenterade 5 mars 2016

In python, I am also getting the same error as Louise.If I try to use raw_input instead its only working for the first two test cases.

Anmäl missbruk
kommenterade 5 mars 2016

Raees, I use python and got exactly the same problem as you. It works only for the first two cases.

Kattis keeps saying ValueError, and if I'm not mistaken, it's about exception handling. And as far as I understand, my code already handle all the exception input it can handle.

Anmäl missbruk
kommenterade 7 mars 2016

Hi,

A quick last minute question. If we try to break the ciphertexts problem and we only break one, to the final amount of points attempted it computes as 2T attempted or the whole 12T of the problem?

Thank you for your help

Anmäl missbruk
kommenterade 10 april 2016

Hi,
Will Homework 2 be uploaded soon? Also, it would be great if the slides from the April lectures were uploaded for those of us who might have missed a lecture.

Anmäl missbruk
Douglas Wikström redigerade 12 april 2016

All handouts in the course will be available here.

General Information
* Course description.
* Instructions for talks.
* Rules for solving problems and handing in solutions.
* Example of compiled solution set and the corresponding LaTeX source. Note that this is an example that should not be used to typeset any real set of solutions. It is only used to illustrate what is expected from students. There will be a separate template for each homework.


Latex and Running Ubuntu in a Virtual Machine on Windows
* The Not So Short Introduction to LaTeX (see also the template above).
* VM Ware Player (free for non-commercial use)
* Download Ubuntu ISO-file
* ubuntu.tar.gz
To install Ubuntu in your VM Ware player, start the player, create a new virtual machine, and browse for the ISO-file. All you need to do is enter your name and password, the rest is taken care of by VM Ware player. When this is done you open a browser inside your Ubuntu and download ubuntu.tar.gz from this page. Look inside the scripts and comment out the things you do not want, the script is reasonably well documented.

Homework Clarification. You need to pick a subset of complete problems that can nominally give 50 T and I points. If the points do not add up to exactly 50 points, then attempt to solve one additional problem partially until you are close to 50 points. It is not the end of the world if it is 51 points or so.

The whole idea is to give you more problems than needed to choose from, because it is more fun, and not to let you cherry pick the easiest subproblems of each problem.

If you want to solve more problems, then insert a section "Additional solutions", where your formally submitted solutions end. I have now promised to correct those as well, but you will not get any formal points for them. 


* Homework 1I. (LaTeX template for your solutions)
* Hints for Problem 1. Remember the following from class:
* Be confident. If you manage to match symbols with a frequency analysis in the first cipher, then you are close to the plaintext. There may be a silly transposition in the end to prevent usage of online tools. Look closely at the plaintexts.
* The Vigenere cipher is only one of several natural instantiations of a general construction where we divide the ciphertexts into blocks of equal size k and encrypt the ith component of each block with a separate key for i=1,...,k. The simple cipher in the original Vigenere is the Ceasar cipher, but we could replace it by one of the other simple ciphers as discussed in class.
* The alphabets of the plaintexts and ciphertexts are identical in the first two challenges and the algorithms operate on this set of symbols.
* In the third challenge ciphertext the ciphertext alphabet is smaller than the plaintext alphabet, so necessarily a plaintext symbol must be mapped into more than one ciphertext symbol, but this is done in a very natural way for computer scientists and a slightly creative frequency analysis reveals what is going on.

* Problem 1: You should ONLY email me the source code packaged according to instruction. The rest of the homework should be submitted according to the rules.

I strongly suggest that you use the tools presented in class systematically. If you do this, then you can break at least two ciphertexts.


* Problem 6(e): Strictly speaking Y is in {0,1}^{n+1}, but you may think of Y either in this way or as a random variable over {0,1}^n, since Pr[X_0=1]=1.


* Typos: "Hoffman" should be "Huffman".



* Homework 2.II. (LaTeX template for your solutions)
* Homework 3.
* Homework 4.
Slides From Lectures
* Lecture 1.
* Lecture 2.
* Lecture 3.
* Lecture 4. (+ discussions about context, modelling, definitions, structure of proofs of security in cryptography...)
* Lecture 5.
* Lecture 6. (+ discussions about: algorithms for elementary arithmetic (sketches of algorithms and running times), different ways of viewing the spaces of plaintexts and ciphertexts, and natural constraints),
* Lecture 7. (+ generic discussion about security models, motivating definitions, and putting discussions about RSA into context)
* Lecture 8.
* Lecture 9.
* Lecture 10.
* Lecture 11.
* Lecture 12.
* Lecture 13.
* Lecture 14.

kommenterade 12 april 2016

Hi,

I think the first problem is missing from the template for homework 2.

Anmäl missbruk
kommenterade 12 april 2016

Problem 2 on Kattis (rsafact) promises products of odd primes, but the sample test case has N=22.

Anmäl missbruk
kommenterade 12 april 2016

Homework 2, problem 3 *

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 15 april 2016

Do you have a preference as to how we are supposed to reference papers for question 5? Given that we are already using LaTeX, the cleanest way would be to use biblatex but that begs of question of where to put the References section.

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 21 april 2016

I have to ask, will we have any answer on Samuel Zackrisson's question?

The task clearly(?) states conditions which the test cases (and therefore possibly the kattis cases as well) do not live up to. 

Answers please, Douglas!

Anmäl missbruk
kommenterade 22 april 2016

Until Douglas replies, here's what I noted to solve it:

[rsafact] on Kattis has two test cases.

Case 1: identical to the sample test case, thus containing input N = 22 ( = 11*2).
Case 2: Contains no even primes (unless my solution is unexpectedly robust).

Thus you can hardcode a check for 22 and then merrily go on trusting the problem specification.

Anmäl missbruk
Lärare kommenterade 22 april 2016

Thank you Samuel!

I added a hint to the handouts page.

Although your solution may work on Kattis, I think you should instead simply right shift until the least significant bit is one. The number of shifts gives the power of the factors of two in your number.

If you want to do this faster for very large numbers, then you should of course loop from the least significant non-zero word upwards until a non-zero word is found and then look closer at that word before you shift the whole number the right number of steps.

Doug

Anmäl missbruk
kommenterade 22 april 2016

Question regarding question 10, hw2, which of these numbers do we actually get to know? Only g^x, u and u^x mod p or do we get to know p, q etc.. as well?

Anmäl missbruk
kommenterade 22 april 2016

Is there a way to compile with the GMP C library in Kattis? When compiling it needs the flag -lgmp with gcc, so in Kattis it does not work.

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 23 april 2016

Aitor: I don't think there is a (good) way to use GMP with kattis. The course "Advanced Algorithms" had the same problem.

Anmäl missbruk
kommenterade 25 april 2016

Can we get the test cases that Kattis checks before the oral exam? Kattis says the output is incorrect but from all the finite test cases that I can try, I haven't seen an incorrect output.

Anmäl missbruk
kommenterade 25 april 2016

Saurav are you using python 3 by any chance? I had issues presumably with I/O that vanished when I switched to python 2 (terrible practice but possibly worth a try)

Anmäl missbruk
kommenterade 26 april 2016

Hey Louise, no I'm using C++. I did not use GMP though, which is probably my issue. But I have an algorithm that would avoid numbers becoming too large.

I just don't understand if the program should be robust to larger inputs, why are the 3-4 test cases that are given on kattis such tiny inputs.  

Anmäl missbruk
kommenterade 27 april 2016

When will HW3 be online? The schedule indicates that it was supposed to be last Friday.

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 4 maj 2016

The link to Kattis provided in questions 6 to 8 is not to the regular one (kth.kattis.scrool.se instead of kth.kattis.com) and the certificate of that website is wrong (expired and unknown issuer) according to my browsers so I can't access it, despite creating a permanent security exception, as Firefox calls it or trying to get through to the dangerous website, as Chrome puts it.

Anmäl missbruk
kommenterade 4 maj 2016

I get through and a 404.

Here are links to the problems from another domain, until Douglas responds.
Elliptic curve arithmetic: https://kth.kattis.com/problems/kth:krypto:ellipticcurvearithm
Feldman: https://kth.kattis.com/problems/kth:krypto:feldman
SHA-256: https://kth.kattis.com/problems/kth:krypto:sha256

Anmäl missbruk
kommenterade 4 maj 2016

Thanks !

Anmäl missbruk
kommenterade 4 maj 2016

In problem 1b: Is e chosen a) randomly or b) as a fixed function of N?

Anmäl missbruk
kommenterade 4 maj 2016

When will the oral exam take place?

Anmäl missbruk
kommenterade 4 maj 2016

We already have the answer to that question in the Google calendar whose link is posted in Deadlines: between Wed. June 1st and Friday June 3rd. To me, the more relevant question would be "when will we be able to register for the oral exam?".

That's an additional concern for international students who would like to (to include more than just those who actually have to) go back home when the term is over.

Anmäl missbruk
kommenterade 13 maj 2016

Hello,

We have a question regarding problem 1 on homework 3. In the problem description you say that \(\mathsf{QR}_N\) is a subgroup of \(\mathbb{Z}_N\). Dou you perhaps mean \(\mathbb{Z}_N^*\) here?

Anmäl missbruk
Lärare kommenterade 13 maj 2016

Dear all,

I do not say "QR_N is a subgroup of Z_N". I say "subgroup QR_N of quadratic residues in Z_N". The residues form a group, so this is what I have in mind.

However, yes, you are reading it correctly, this is a subgroup of Z_N*. It is a good idea to ask oneself: What is the order of that subgroup? (this is rather important in the construction, otherwise we would not bother with restricting primes in this way of an RSA modulus)

/Doug

Anmäl missbruk
En användare har tagit bort sin kommentar
kommenterade 13 maj 2016

Same for me. Interesting. My schedule is suddenly empty in all my courses. It seems that all schedules mysteriously have disappeared.'); drop table schedules; --

Anmäl missbruk
4 personer gillar kommentaren
kommenterade 19 maj 2016

In question 1e, may A evaluate H multiple times?

One possible interpretation is that A may only do one evaluation of H, and that evaluation is on the input m.

Another possible interpretation is that A may call H as many times as it wants, but at least one of these calls must be with the input m.

Anmäl missbruk
Lärare kommenterade 19 maj 2016

It can ask as many times as it likes as for any other oracle. A priori it does not even need to call it with m, but of course it has to do that to have a chance to be successful.

Anmäl missbruk
kommenterade 19 maj 2016

The latex template for HW3 incorrectly says "Homework 1".

Anmäl missbruk
kommenterade 19 maj 2016

In case the homework has already been printed and submitted, is it necessary to reprint the first page after correcting that?

Anmäl missbruk
kommenterade 20 maj 2016

yes/no question:
In problem 1(e+), does A have access to any random oracle / source of randomness other than H & Sign?

Anmäl missbruk
kommenterade 7 juni 2016

Hello,

I was wondering about the AES problem from homework 1.

I have made it work for all testcases except the last one (Time limit exceeded). I used java, with "BigInteger" foolishly it might seem :). I was just wondering if anyone has made it work with java, and bitarithmetics with datatype "int" instead. 

This because i am considering if it is really neccesary to start a c/c++ adventure.

Thankfull for any response. 
Daniel

Anmäl missbruk
kommenterade 7 juni 2016

Why would you use "int" when each operation is performed either on bits or on bytes?

Anmäl missbruk
kommenterade 7 juni 2016

Javas bitwise arithmetics are for ints. Of course i could typecast it from byte to int for each operation. But seems more time consuming

Anmäl missbruk
kommenterade 7 juni 2016

My bad, I went back to review my code more carefully and I do have an awful lot of casts from int to byte (and not so many, if any, the other way around) in there, but I'm still way below the 10s limit, despite being far from reaching the top 10.

Anmäl missbruk
kommenterade 7 juni 2016

Ok, nice to hear!

FYI, with BigInteger it took like 90 sec on my own testcases 10^6 large.

Anmäl missbruk
kommenterade 8 juni 2016

I've done it in Java with byte and int. In fact I've tried to use only byte. I only hold the Sbox and the rcon table in arrays of type int. I do arithmetic operations on bytes and since the result is in int I do a cast before assignment. 

Anmäl missbruk
kommenterade 8 juni 2016

By the way, If you have speed problem, I suggest to take a look at your byte multiplication function which should be used at mixColumns step.
I had similar problem with my naive implementation of byte multiplication, then I found the "FFMul" algorithm which saved me. Here is a paper about it : http://www.texmacs.org/joris/ffmul/ffmul.pdf

There is also a sample implementation of FFmul in the book "The laws of cryptography" by "Neal R. Wagner"

Anmäl missbruk