Nyhetsflöde
Logga in till din kurswebb
Du är inte inloggad på KTH så innehållet är inte anpassat efter dina val.
Har du frågor om kursen?
Om du är registrerad på en aktuell kursomgång, se kursrummet i Canvas. Du hittar rätt kursrum under "Kurser" i personliga menyn.
Är du inte registrerad, se Kurs-PM för DD2448 eller kontakta din studentexpedition, studievägledare, eller utbilningskansli.
I Nyhetsflödet hittar du uppdateringar på sidor, schema och inlägg från lärare (när de även behöver nå tidigare registrerade studenter).
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.
Is there a typo in problem 6c?
We input a 128-bit random variable into a function on 256-bit inputs.
No, but information is missing. You can set the top 128 bits to zero.
Thank you for pointing this out to everybody!
Problem 9 clarification: We assume n is even for the Feistel network, right?
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.
Yes, n is always even in a Feistel network.
Problem 6(e): You may think of Y either way, since Pr[X_0=1]=1.
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?
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
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!
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.
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!
Second option: you get a bit stream through standard input.
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 :)
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 :-)
Please do not ask questions like that of Raees above. You need to think about it yourself and simply read the problem statement carefully.
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!
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.
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.
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,
Alfonso, you can use putchar() to write chars to stdout. It worked for me, but maybe there is a better way.
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.
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.
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
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.
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.
Hi,
I think the first problem is missing from the template for homework 2.
Problem 2 on Kattis (rsafact) promises products of odd primes, but the sample test case has N=22.
Homework 2, problem 3 *
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.
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!
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.
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
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?
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.
Aitor: I don't think there is a (good) way to use GMP with kattis. The course "Advanced Algorithms" had the same problem.
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.
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)
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.
When will HW3 be online? The schedule indicates that it was supposed to be last Friday.
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.
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
Thanks !
In problem 1b: Is e chosen a) randomly or b) as a fixed function of N?
When will the oral exam take place?
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.
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?
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
V22
Same for me. Interesting. My schedule is suddenly empty in all my courses. It seems that all schedules mysteriously have disappeared.'); drop table schedules; --
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.
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.
The latex template for HW3 incorrectly says "Homework 1".
In case the homework has already been printed and submitted, is it necessary to reprint the first page after correcting that?
yes/no question:
In problem 1(e+), does A have access to any random oracle / source of randomness other than H & Sign?
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
Why would you use "int" when each operation is performed either on bits or on bytes?
Javas bitwise arithmetics are for ints. Of course i could typecast it from byte to int for each operation. But seems more time consuming
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.
Ok, nice to hear!
FYI, with BigInteger it took like 90 sec on my own testcases 10^6 large.
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.
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"
Schemahandläggare redigerade 29 januari 2016
V122
Schemahandläggare redigerade 29 januari 2016
B24V22
Schemahandläggare redigerade 29 januari 2016
V122
Schemahandläggare redigerade 29 januari 2016
B24V22
Schemahandläggare redigerade 29 januari 2016
V132
Schemahandläggare redigerade 29 januari 2016
B24V22
Schemahandläggare redigerade 29 januari 2016
B24V32
Schemahandläggare redigerade 29 januari 2016
B24V3
In question 7 of homework 1, can we assume that "Hoffman" is a typo and should be read "Huffman"?