Projekt
Projects
There are three mandatory projects in the course and they need to be approved before the exam. Any questions should be directed to Vu, preferably at the actual exercise session, who will answer questions regarding the projects. Please recall your group number, and the results will be shown after your group number. If you cannot attend a particular exercise session, you are welcome to visit Vu's office (WHERE: E:3119d, weeks 1-7) during his office hours listed below or post your question on Canvas (Discussion thread).
- Monday: 10:00-12:00
- Wednesdays: 10:00–12:00
- Thursdays: 10:00–12:00
- Fridays: 15:00–17:00
Qian (office: E3152c) is the project examiner and his office hours are:
- Monday: 13:00–15:00
- Fridays: 13:00–15:00
Project | Hand-in Deadline | Presentation deadline |
1: Factoring Algorithm | Friday November 18th | Friday December 2th |
2: Shift Register Sequences | Friday December 2th | Friday December 9th |
3: Correlation Attacks | Friday December 9th | Friday December 16th |
Information
- All projects must be done in groups of 1-2 students. Two per group is strongly recommended. 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 Vu with your name(s). If you don't have anyone to work with, indicate so in your mail and we'll try to find someone for you.
- To pass a project you have to hand in a written report and also present your solution to Qian. You need to present your solution during Qian's office hours. Present your solution soon after handing it in and no later than the deadlines specified above! See office hours above.
- Send in your written report per e-mail, send a pdf-file named project_<number>_group_<number>.pdf to qian.guo@eit.lth.se. Include everything in your report; code, explanations, solutions, and so on. Explain the vital parts of your code in a human-readable way. Note that your document may automatically be checked for plagiarism using the Urkund anti-plagiarism system. For more details on this, see here. Do not send multiple files, do not compress your report pdf, and do not use other formats. Urkund does not support this.
- You are 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 have done it.
Assistance and presentation
You can use the exercise session for asking questions about the projects, but the exercise session should mainly be used for exercises.
Questions about the projects should be on a conceptual level. Students taking this course are expected to have taken a couple of programming courses. We will not read your code.
After submitting the report you can present it as soon as there is an office hour (or exercise session).
Present your project while you still have it in recently used memory. You will need to explain some concepts or ideas and there might be follow-up questions that 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 projects is Friday, December 16. 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++/Python 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.
Hint: Java and BigInteger can make your job easier in some cases.
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 written report should contain the following things:
- The solution to Exercise 1.
- The solution to Exercise 2.
- The solution to Exercise 3: 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 4.
- The number of working hours used for the project.
Send the report to Qian as a pdf file as specified above.
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. Or C++ Big Integer Library, which can be found here.
Gaussian elimination
We provide the tool GaussBin.exe (win: GaussBin.cpp, unix(gcc, linker flags -lc++ or -lstdc++ may be useful): 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 your own Gauss-tool), you can either execute the tool manually or run it from Java, for instance by using the Runtime or ProcessBuilder 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 - 1 = 4095 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.
Some very basic and general hints on debugging and program efficiency can be found here.
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, 3 and 4. Only answers won’t be accepted.
- The solution/answers to computer exercises 1, 2, 3 and 4. Only answers won’t be accepted.
- The De Bruijn sequence you’ve constructed in paper exercise 5 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 Bruijn-ness (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 Qian as a pdf file. 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
Some hints and pointers on factoring in finite fields can be found here.
Also, when using Maple, you will probably need to use the Maple command ConvertIn before you use the order command.
For fun: http://www.math.ubc.ca/~anstee/math443/DeBruijnCardTrick.pdf
Project 3 – Correlation Attacks
Here you can download the project description.
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
Reports
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, are written in binary representation.
- The best (maximum biased) probabilities p for the initial states of the 3 LFSRs.
Send the report to Qian as a pdf file as specified above. Please include everything in the pdf, even the source code.
Additional hints and comments
When you recover the key, then, afterward, 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 the most far away from the value 0.5, i.e., you are looking for the key K, which maximizes |0.5-p*|.