Math549 Coding Theory and Cryptography

2025-05-12 Admin 写评论

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Math549 Coding Theory and Cryptography
Project: Avalanche Criterion
Due date: May 16th, 11:59pm

The Avalanche Criterion (AC) is a process that happens in block ciphers. Objectively, you look to measure the amount of change in the output bits of a cipher when you change only one input bit. Loosely speaking, the strict avalanche criterion (SAC) is the most desired version of this affect, but good AC is generally speaking sufficient.

There are two components to this project.

1. Write a short essay outlining what AC and SAC is. You will need to use more than just the Wikipedia entry about this, but that would certainly be a start. There are many pieces of information about AC and SAC available on the web, some better than others (of course!). This component of the project is easily the shorter of the two, but you will need to truly understand the concept properly to give a meaningful answer to the second component.

2. You are now going to study avalanche criteria on something quite simple: namely, where we use a linear substitution cipher as a block cipher. How to do so is described below. Ultimately, your goal is to analyze the linear substitution cipher for AC and conclude whether, in your opinion, the linear substitution cipher offers good AC or not. Your report should give a reasoned answer as to why you end up with the conclusion you make. During your analysis, you may or may not observe some instances of a linear substitution cipher producing SAC (say, for a specific choice of key). If you do, you should absolutely report this. If you do not, you should also make a statement to that effect.

Within this question is a hidden problem: Namely, how do you measure AC and SAC? There are a number of sensible ways to do so. This is something you will have to determine as part of your study. To this end, within your project description you must include a section detailing what you decided to use for measuring AC, and why you think it is a reasonable way to measure it.

How to use a linear substitution cipher as a block ciper
We design a block cipher on bit blocks of length k. To use a linear substitution cipher, we need to do three things:

  • Choose the bit length k. We will then be working with integers modulo N = 2k .
  • Choose the key for the encryption function: this is a pair of integers (a, b), where 3 ≤ a ≤ N − 1 is odd and 0 ≤ b ≤ N − 1 is any number.This determines the encryption function: Ea,b(x) = ax + b mod N. Changing the choice of the pair (a, b) clearly changes the encryption function E.
  • We also need to be able to convert integers to bit strings. This is literally the application of the division algorithm for finding the base expansion with base 2. This was covered in the lecture on the Division Algorithm and it’s Applications. You should re-watch that if you don’t recall – it is pretty much the first application described in that lecture – but basically, for binary, it involves repeated division by 2.
So how do those 3 things gives us a block cipher? Let me show you using just 2 bits, and additionally give you a starter on how to go about analyzing AC. We set k = 2 and so N = 22 = 4. There is consequently just 1 choice for a (3), and 4 choices for b (0,1,2,3). I will choose a = 3, b = 2.

The encryption function for this example is therefore E(x) = 3x + 2 mod 4. I can now look at every result from this function: The message space involves just the four numbers 0 ≤ x ≤ N −1 = 3. We have


I now convert my inputs and outputs into binary sequences using the base expansion technique, and reproduce the table:

This final table represents the linear subsitution cipher acting as a block cipher on 2 bit blocks. If I now want to look at the AC, then I want to look at how changing 1 bit in the input changes the output. For example, changing one bit of input from an initial input of 00 will either produce an input of 01 or 10, and I look at how the output changes. Below I have tabulated all of the possibilities:
Original Input and Output

Inputs 1 bit away and their Output
 Inputs 1 bit away and their Output
 Number of output bits changed
00 → 10

01 → 01

10 → 00

2

1

01 → 01

00 → 10

11 → 11

2

1

10 → 00

00 → 10

11 → 11

1

2

11 → 11

01 → 01

10 → 00

1

2

From this, I can see that the number of bits that changes per 1 bit of input changing was 1.5 on average. If I wanted to analyze a 2 bit linear substitution cipher for AC, I would need to do this for every choice of possible key. There are 4 possible keys in this example and after doing the above for each of them, I would find that this cipher looks quite good. However, this is not a surprise, because at least 1 output bit has to change whenever I change an input bit because the cipher is a bijection – that means for a 2 bit linear cipher, I was always guaranteed a minimum change of 50% of the output bits when I changed an input bit. When I increase k, I am still going to be guaranteed at least 1 bit of change for the same reason, but I am not guaranteed any more than that via this argument. That is why we need to do an analysis for larger bit lengths.

For your project, you must analyze at least the case k = 3, and preferably k = 4 as well. Writing some code in whatever is your preferred programming language will make this much simpler (and you’ll probably be able to analyze even larger bit lengths if you so desire). It is possible to do the k = 3  casecompletely by hand, but it does take a good amount of time (there are 24 possible encryption functions in that case, hence the reason it is a decent amount of work!). Of course, I would absolutely recommendyou do this with some programming, but ultimately it is up to you. I will say that without looking at k= 4 too (where there are 7 × 16 = 112 possible functions), you cannot really say a lot. Before setting this project the first time, I had no idea what to expect for the AC of a linear substitution cipher. I won’t say anything about what you should expect as I think it best to leave you to make your own conclusions. One obvious thing you really should consider is whether the AC performance of a linear substitution cipher decreases as you increase the bit length. To this end, you could do a partial analysis (say a couple of randomly chosen keys) for larger bit lengths to see if you can make any partial conclusions.

Finally, you might wonder why we would even consider using a linear subsitution cipher when we know they are insecure. The point is that if they did offer good avalanche criteria, then you could use them as one step in a multiple step encryption process, where other steps would make sure the cipher was not linear. This would likely produce a non-linear cipher with good avalanche affect. Since linear substitution is a very quick encryption step, it could still be useful. At the end of this project you will probably be able to conclude if it offers any value as a cipher technique.

All submissions must be in a single PDF file through Canvas before the deadline.

Assessment Value: 50 points

发表评论

电子邮件地址不会被公开。 必填项已用*标注