EDI051 Kryptoteknik
2010/2011 Ht2
Projekt
Projects
There are three mandatory projects in the course and they need to be approved before the exam. There is a fourth, optional project. Martin will answer questions regarding the projects. Please recall your group number. The results will be available on the result
page.
Information
- All the projects must be done in a
group of 1 or, maximum, 2 students. Each group will be assigned a unique number affecting the solutions to numerical instances of the problems. In order to get a group number, send a mail to Martin with your name(s). If you don't want to work alone, but don't have anyone to work with, indicate so in your mail and we'll try to find someone for you.
- If you send in the report per e-mail, send it to Martin and include the project title and your group number in the subject.
- To pass a project you
have to hand in a report and also present your solution to Martin. Do this soon after handing it in and no later than December 9! See below for office hours.
- It is ok (and encouraged!) to discuss the projects with other groups
but you are not allowed to copy any source code from another group.
- You
have to be able to answer questions related to the project. That is, you
should understand what you have done and why you’ve done it.
Assistance and presentation
Martin will answer questions
regarding the projects during the time slots below (room E:3120c).
You are welcome to present your project in these time slots as well (no need for an appointment, just show up). Martin is away the entire week 6 (29/11-3/12).
Please respect these time slots!
- Monday: 9-10
- Tuesday: 9-10, 14-16
- Wednesday: 9-10
- Thursday: 15-16
Note that it is a good idea to present your project while you still have it in recently used memory. In other words, don't save the projects until the last week. Don't try to present the project in a pop-in for a minute before running to class, since you will need to explain some concepts or ideas and there might be follow-up questions which need some thinking.
As always, being late with a project only delays the following projects as well.
Help yourself by starting early! The absolutely last day for presenting
the project is Thursday December 9. It is probably a good idea to present earlier in order to
avoid congestion...
Project
1 – Factoring algorithm
Here you can download the project description.
How to
do the project
Implement the algorithm in any
programming language (such as Java/C++ or whatever you prefer). The algorithm
deals with large numbers. In Java, you can use the BigInteger
class to represent integers of arbitrary size. The usage of the class is
straightforward, take a look at the documentation.
If you prefer to use C++, we provide you with the class LongInt (see the
tools section below for more details). You are allowed to substitute the
tools we suggest with other of similar functionality.
Input
Each group is given a unique
number to factorize in Exercise 3. Check the groupings page if you
don’t know which group you belong to. Below is the number N for the different
groups.
Input for group
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Report
The report should contain the following things:
- The solution to exercise 1.
- The solution to exercise 2: The number N and its factorization, the time taken to get the solution (running time) and printouts of the program you have written.
- Voluntarily you can include the answer to exercise 3.
- The number of working hours used for the project.
Send the report to Martin as a pdf file or leave a printout
in the slot "Övriga kurser" at the third floor.
Tools
In this section we provide you
with some tools to make the project easier for you. Which ones you need
depends on your choice of programming language and how much you want to
implement yourself.
Large
integers in C++ (LongInt)
If you use C++ you might want
to use our LongInt library to represent large integers. It contains one
object, the LongInt class, which can work with large numbers up to 2^960. It
can do all the necessary operations involved in the project. We also have an
example of the usage of the class in the file LongIntExample.cpp.
For Windows users: LongInt.h
LongIntExample.cpp
For UNIX users (gcc): LongInt.h
LongIntExample.cpp
The expected output from
running LongIntExample.cpp is
x: [+ 1]
y: [+ 42]
z: [+ 42]
Stream Initialization of z: [+ 4151368860]
x =z*y: [+ 174357492120]
z*=y : [+ 174357492120]
Logarithm by the base 2: log(z) = 37.343257
z=sqrt(z): [+ 417561]
z*z: [+ 174357188721]
Modulo z%y: [+ 39]
Division z/y: [+ 9941]
The (long)-valued result for (z) mod 42: 39
Division by (long)-value (z) div 42: [+ 9941]
92154678365472 = 2^5 * 2879833698921
In case the Windows source
doesn’t work in your Windows compiler, try the UNIX version.
Another option is to use the
GMP library. Information about it can be found here.
Gaussian
elimination
We provide the tool GaussBin.exe
(win: GaussBin.cpp, unix(gcc): GaussBin.cpp)
for solving a linear system of equations when X*M=(0) mod 2. You need to call
this program with 2 parameters - the name of the input file, and the name of
the output file. It’s written in C++ and if you use that language you might
as well include the source code in your implementation. If you use Java (and
aren’t eager to write an own Gauss-tool), you can either execute the tool
manually or run it from Java, for instance by using the Runtime
class. The structures of the input and output files are specified
like this:
Usage:
GaussBin.exe <input_file> <output_file>
<input_file>
- description:
M N - first line contains the matrix size M*N
M denotes the number of (r^2 mod N) - numbers
N denotes the factor base size
x11 x12 ... x1N - the integer nonnegative values of the matrix
x21 x22 ... x2N will be taken modulo 2, and then the Gaussian
...
elimination algorithm will be performed.
xM1 xM2 ... xMN
<output_file>
- description:
R - the number of solutions. If there are a lot of solutions,
then it will be truncated to 2^12 solutions.
s11 s12 ... s1M - each line contains a solution vector. i.e. if
s21 s22 ... s2M we consider solution i, then si1, si2, ..., siM
...
denote the correspondent rows from the
...
input_file that we need to sum in order to get
sR1 sR2 ... sRM (0) modulo 2.
Square
roots in Java
The BigInteger
class in Java class does not support calculation of square roots. The easiest
way around this is probably to write a function yourself. The following code
is fairly fast:
/** Calculate the square
root of a BigInteger in logarithmic time */
public BigInteger
squareRoot(BigInteger x) {
BigInteger
right = x, left = BigInteger.ZERO, mid;
while(right.subtract(left).compareTo(BigInteger.ONE)
> 0) {
mid
= (right.add(left)).shiftRight(1);
if(mid.multiply(mid).compareTo(x) >
0)
right
= mid;
else
left
= mid;
}
return
left;
}
It’s not the most optimal way of
writing a square root function, but it doesn’t matter since it won’t be the
bottleneck anyway. The function
is similar to binary search, i.e. the interval containing the square root is
halved until the root is found.
Prime
generator
The file prim_2_24.rar
contains a text file, 2_24.txt, which contains the first 2^24 prime numbers. It was
generated using the program GenPrimes.cpp
. You can take a look at the source and extract the part that generates the
primes (and ignore the file I/O) if you’d like to generate the primes by
yourself instead of reading them from the file. That part of the code only
needs slightly modifications to work in Java.
Additional
hints and comments
Regarding the parameters for your program: Choose L =
2^10. Prepare the matrix to have the size (L+10)*L,
that is, you generate L+10 numbers. Make sure it doesn’t contain any equal
rows since the GaussBin program will remove them (which may result in too few
equations). Using those parameters will make the probability of finding a
solution very high.
In case you use C++ with the
LongInt class: Note that you should Not use z.powfn(2) in order to square z. Use z*z instead, since the powfn truncates the result.
Please verify that your
obtained primes are correct by checking that N = pq yourself. Finally, if
your program manages to factor the first two of the three examples given in
the end of the description file, it does NOT mean that your program is almost
working. Calculating gcd(a-b,N) will always factor N if a-b is a multiple of one of the primes. If the primes
are small it will, after some tries, by chance try a number that will work.
Project
2 – Shift Register Sequences
Here you can download the project
description.
How to
do the project
First make sure you are
familiar with basic abstract algebra and linear shift registers. In order to
do the laboratory exercises you will need to use Maple. For the last exercise
(De Bruijn sequences), we suggest you to use a programming language such as Java/C++
or even Matlab if you know it very well. First do the paper exercises by hand.
Then continue with the computer exercises. Note that paper exercises are
supposed to be done manually, whereas in computer exercises you should use
Maple as a powerful tool to solve such problems. Finally, do the last
exercise using the programming language of your choice.
Make sure your results are
correct! You can verify the answers to the paper exercises in Maple. Use the
provided tool to verify the correctness of your De Bruijn sequence.
Report
We expect your report to
contain the following things:
- The
solutions/answers to paper exercise 1, 2 and 3. Only answers won’t be
accepted.
- The
solution/answers to computer exercises 1, 2 and 3. Only answers won’t be
accepted.
- The De Bruijn
sequence you’ve constructed in paper exercise 4 and a figure of the
corresponding shift register.
- The program which
generates the De Bruijn sequence in computer exercise 5. The generated
sequence must pass the test on De
Bruijness (see the tools section)
- The number of
working hours used for the project
Note: You must be able to explain everything you have
done at the presentation. That includes your solutions to the paper exercises,
which Maple commands you used to solve the computer exercises and so on.
Send the report to Martin as a pdf file or leave a printout
in the slot "Övriga kurser" at the third floor.
Please include everything in the pdf, even the source code (of
course you don’t have to include your hand made calculations, but be prepared to
hand them in and to explain them on the presentation).
Tools
We only provide you with one
tool for this project, Check_LE4.c.
You can take a look at the source code here. It’s a program for verifying
that your De Bruijn sequence in laboratory exercise 5 indeed is a De Bruijn
sequence. Make sure your obtained sequence passes the program! The compiled Windows
version can be downloaded here.
Additional
hints and comments
If you don’t
want to find a primitive polynomial by trial, you can use Google to find a list
of primitive polynomials. However, don’t forget to verify that the one you
pick indeed is primitive.
Project 3 – Correlation Attacks
Here you can download the project description (updated November 18, 11:30).
The simplest way to solve the
problem stated in the project is to use a programming Language such as C/C++,
Java, ect. If you have another suggestion of how to solve the project, then
you're welcome to discuss it.
Input
Each group is given a unique
sequence to find the key for.
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Report
We expect your report to
contain the following things:
- The source code
for the program you've written.
- The key, or
initial states of the 3 LFSRs, written in binary representation.
- The best (maximum
biased) probabilities p for the initial states of the 3 LFSRs.
Send the report to Martin as a pdf file or leave a printout
in the slot "Övriga kurser" at the third floor.
Please include everything in the pdf, even the source.
Additional
hints and comments
When you recover the key then, afterwards,
please check yourself whether it is correct, i.e.,
that the LFSR-based stream cipher
produces the sequence that you expect it to.
You need to find
a value p*, which is most far away from the value 0.5, i.e. you are
looking for the key K which maximizes |0.5-p*|.
Project
4 – Learning about DES (optional)
Here you can download the project
description.
Note that this project is optional.
How to
do the project
For the four paper exercises, all
you need is a paper and a pencil. For the two computer exercises you can
use the programming language of your choice. Below, we provide all tables
needed in DES so that you don't have to waste time retyping it from the description.
Input
Each group is given a unique
sequence to find the key for.
00
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
Report
Feel free to hand in a report,
containing e.g., the following things:
- The printed
version of your program.
- Solutions for the six
paper and computer exercises.
- The number of
working hours you spent for the project.
Send the report to Martin as a pdf file or leave a printout
in the slot "Övriga kurser" at the third floor.
Please include everything in the pdf, even the source.
Tools
We provide the tables used in
DES. For C/C++:
des_cnst.h. For Java: Constants.java.
The files contain the boxes
and permutation tables for DES. Don't forget that in the tables the indices
are starting from 1, but in Java/C/C++ all indices start from 0.
Additional
hints and comments
When implementing the DES
algorithm, be careful with indices.
Use the example in the
description to make sure that intermediate values are correct.
Print out your intermediate values and compare with the expected ones!
