# 密碼工程 Quiz7
###### tags: `密碼工程`

## Q1

### Usage

我給的程式讓使用者指定要輸出幾個 random byte (注意不是 bit) ，輸出到 stdout ，輸出的資料為人眼部可讀的 binary data 。以下示範輸出 1MB (1048576 byte = 8388608 bit) 的資料到檔案 random_output 。

python3 quiz7.py 1048576 > random_output

生成的過程蠻久的，需要耐心。

### 理論

BBS 內部的狀態為一個大數 $s_i$ ，並定義其下一時刻狀態為 $s_{i+1}={s_i}^2 \pmod M$ ，其中 $M=pq$ 且 $p$ 與 $q$ 為兩大質數，又 $p=q=3 \pmod 4$ 。

種子 $s_0 \in [2, M)$ 必須與 $m$ 互質，即 $s_0$ 非 $p$ 或 $q$ 之倍數。但由於隨意生成之種子 $s_0$ 與 $M$ 在大數情況下互質的機率極高，通常可以不用檢驗。

BBS 之輸出為其狀態 $s_i$ 之 parity 。

這個程式非常耗時的原因可以歸納為兩點：
- Python 的速度本來就慢
- 大量的大數運算

### 程式碼解說

我選擇實作 BBS 亂數生成器。以下為 code

class BBS:

    def __init__(self):
        def tester(n):
            return n & 0b11 == 0b11 and test_miller_rabin(n, 100)

        def generate_random_prime(bits):

            ret = random.getrandbits(bits)
            while not tester(ret):
                ret = random.getrandbits(bits)
            return ret

        p = generate_random_prime(512)
        q = generate_random_prime(512)
        self.M = p * q
        self.state = random.randint(2, self.M - 1)

    def next(self):
        def cal_parity(n):
            ret = 0
            while n > 0:
                if n & 1 == 1:
                    ret += 1
                n >>= 1
            return ret & 1

        self.state = pow(self.state, 2, self.M)
        return cal_parity(self.state)

    def next_byte(self):
        ret = 0
        for _ in range(8):
            ret <<= 1
            ret |= self.next()
        return ret.to_bytes(1, 'big')

這個類別代表一個 BBS 亂數生成器。呼叫其方法 next 返回其下一位輸出 $1$ 或 $0$ ，呼叫 next_byte 返回其下八位輸出所組成的一個 byte 。

函數 generate_random_prime(x) 隨機生成一個合法的 $x$ 位大質數，其透過米勒篩法檢驗隨機生成之大數。米勒篩法的函數不附，因為其與 BBS 無關，程式碼可見繳交之檔案。本程式選擇生成 512 位的大數。

### 檢驗結果

我生成一個 768KB 的檔案，使用 SP 800-221 檢驗進行各種檢驗， bit stream 為 589824 、 stream 數量為 10 。所有檢驗均通過。

------------------------------------------------------------------------------
RESULTS FOR THE UNIFORMITY OF P-VALUES AND THE PROPORTION OF PASSING SEQUENCES
------------------------------------------------------------------------------
   generator is <../dump768>
------------------------------------------------------------------------------
 C1  C2  C3  C4  C5  C6  C7  C8  C9 C10  P-VALUE  PROPORTION  STATISTICAL TEST
------------------------------------------------------------------------------
  0   1   1   0   1   1   1   1   2   2  0.911413     10/10      Frequency
  0   1   0   1   2   3   0   2   0   1  0.350485     10/10      BlockFrequency
  1   1   0   1   2   2   0   2   0   1  0.739918     10/10      CumulativeSums
  0   1   1   2   1   1   1   1   0   2  0.911413     10/10      CumulativeSums
  1   3   2   0   1   0   2   0   1   0  0.350485     10/10      Runs
  0   2   1   1   0   2   0   3   1   0  0.350485     10/10      LongestRun
  2   1   0   0   1   1   4   0   0   1  0.122325     10/10      Rank
  2   0   1   3   1   0   2   0   0   1  0.350485     10/10      FFT
  3   1   0   3   0   0   1   0   1   1  0.213309     10/10      NonOverlappingTemplate
  1   0   1   1   2   2   0   2   1   0  0.739918     10/10      NonOverlappingTemplate
  ... 略
  2   0   0   1   2   0   0   2   2   1  0.534146     10/10      OverlappingTemplate
  1   0   0   1   1   1   2   1   1   2  0.911413     10/10      Universal
  2   0   2   1   1   1   1   0   1   1  0.911413     10/10      ApproximateEntropy
  1   1   1   0   3   0   0   1   1   0     ----       8/8       RandomExcursions
  2   0   1   1   0   1   0   0   2   1     ----       8/8       RandomExcursions
  0   1   2   1   1   0   0   2   1   0     ----       8/8       RandomExcursions
  0   0   1   0   0   3   1   1   0   2     ----       8/8       RandomExcursions
  0   0   1   1   0   1   0   4   1   0     ----       8/8       RandomExcursions
  1   0   0   0   0   4   2   0   1   0     ----       8/8       RandomExcursions
  1   1   0   0   1   4   0   0   0   1     ----       8/8       RandomExcursions
  2   2   0   2   0   0   0   0   2   0     ----       8/8       RandomExcursions
  1   1   0   1   0   0   1   1   3   0     ----       8/8       RandomExcursionsVariant
  1   1   1   0   1   0   1   2   1   0     ----       8/8       RandomExcursionsVariant
  ... 略
  0   2   1   0   0   2   2   2   1   0  0.534146     10/10      Serial
  0   1   3   2   0   0   2   0   2   0  0.213309     10/10      Serial
  1   3   0   1   0   0   2   2   1   0  0.350485     10/10      LinearComplexity


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
The minimum pass rate for each statistical test with the exception of the
random excursion (variant) test is approximately = 8 for a
sample size = 10 binary sequences.

The minimum pass rate for the random excursion (variant) test
is approximately = 7 for a sample size = 8 binary sequences.

For further guidelines construct a probability table using the MAPLE program
provided in the addendum section of the documentation.
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

然後用 AIS-31 檢驗，所有測驗都通過。輸出結果太長，不附。

## Q2

### 1) What is the probability of 2 people having the same birthday X?

$\dfrac{365\times1}{365\times365}=365^{-1}$

### 2) What is the probability of 3 people having the same birthday Y?

$\dfrac{365\times1\times1}{365\times365\times365}=365^{-2}$

### 3) What is the probability of 4 people having the same birthday Z?

$\dfrac{365\times1\times1\times1}{365\times365\times365\times365}=365^{-3}$

### 4) If there are 50 students in classroom, what is the probability that 2 of them have the same birthday?

#### 題目解讀方式之一：教室中存在兩個人，其生日相同的機率。

先計算沒有人生日相同的機率 $p'=\dfrac{365\times364\times\cdots\times316}{365^{50}} \approx 0.029626$ 。

因此有人生日相同的機率約為 $p=1-p' \approx 0.970374$ 。

#### 題目解讀方式之二：教室中存在兩個人其生日相同，且這兩人是教室中唯一一對生日相同者的機率。

$$\dfrac{\dbinom{50}{2}\dbinom{365}{49}\cdot 49!}{365^{50}} \approx 0.114849$$