News feed

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

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.

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"