Projects

 

SEE CANVAS!

 

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 ??

Thomas(office: E3118d) is the second project supervisor and 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 24th	Tuesday November 28
2: Shift Register Sequences	Friday December 2th	Tuesday December 5th
3: Correlation Attacks	Friday December 9th	Tuesday December 13th

Information TO BE UPDATED

• 
  

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:

1. The solution to Exercise 1.
2. The solution to Exercise 2.
3. 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.
4. Voluntarily you can include the answer to exercise 4.
5. 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:

1. The solutions/answers to paper exercise 1, 2, 3 and 4. Only answers won’t be accepted.
2. The solution/answers to computer exercises 1, 2, 3 and 4. Only answers won’t be accepted.
3. The De Bruijn sequence you’ve constructed in paper exercise 5 and a figure of the corresponding shift register.
4. 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).
5. 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:

1. The source code for the program you've written.
2. The key, or initial states of the 3 LFSRs, are written in binary representation.
3. 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*|.