Random trong python liệu có thật sự 'random'? Dự đoán kết quả hàm random() sử dụng thuật toán MersenneTwister generator (MT19937)

Mở đầu

Trong cuộc sống ta luôn gặp những điều ngẫu nhiên. Nhưng có khi nào bạn tự hỏi rằng những sự vật sự việc đó có thực sự ngẫu nhiên không? Tiết lộ cho các bạn rằng tất cả chúng đều không hề ngẫu nhiên, đều có quy luật cả. Nhưng vì quy luật có chúng đôi khi quá phức tạp nên chúng ta có thể tạm coi chúng là ngẫu nhiên.

Hơi khó hiểu phải không ? để mình lấy ví dụ về việc tung 1 đồng xu rồi xác định sấp ngửa nhé. Chắc hản các bạn sẽ nghĩ rằng việc chúng ta thu được sấp hay ngữa đều là ngẫu nhiên thôi đúng không? Nhưng thực ra chúng bị chi phối bởi những quy luật vật lý cơ học cổ điển. Ở một mức độ phức tạp nào đó ta hoàn toàn có thể dùng máy tính tính toán kết quả dựa vào vị trí, vận tốc và gia tốc chính xác khi thả rơi đồng xu để xác định được kết quả.

Hàm random() trong python hay một số ngôn ngữ khác cũng vậy. Thực ra nó được ẩn dấu sau các thuật toán phức tạp để tính toán và đưa ra cho ta một con số giả ngẫu nhiên. Dựa vào một số dữ kiện ban đầu vào chút tính toán ta hoàn toàn có thể đoán được kết quả random() mà hàm này trả về. Sau đây mình sẽ giới thiệu cho các bạn về cách tính toán kết quả của hàm random trong python. Mặc định python dùng thuật toán MersenneTwister generator nên phương pháp mình giới thiệu sau đây có thể áp dụng cho một số ngôn ngữ khác cũng sử dụng thuật toán này.

Giới thiệu về thuật toán MersenneTwister generator (MT19937)

Đây là đoạn code thực hiện random 1 số 32 bit trong python:

N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff

mt = [0 for i in xrange(624)]
mti = N + 1


def init_genrand(s):
    global mti
    global mt
    mt[0] = s & 0xffffffff
    for mti in range(1, N, 1):
        mt[mti] = 1812433253 * (mt[mti - 1] ^ (mt[mti - 1] >> 30)) + mti
        mt[mti] &= 0xffffffff


def init_by_array(init_key, key_length):
    init_genrand(19650218)
    i = 1
    j = 0
    k = N if N > key_length else key_length
    for k in range(k, 0, -1):
        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1664525)) + init_key[j] + j
        mt[i] &= 0xffffffff
        i += 1
        j += 1
        if i >= N:
            mt[0] = mt[N - 1]
            i = 1
        if j >= key_length:
            j = 0

    for k in range(N - 1, 0, -1):
        mt[i] = (mt[i] ^ ((mt[i - 1] ^ (mt[i - 1] >> 30)) * 1566083941)) - i
        mt[i] &= 0xffffffff
        i += 1
        if i >= N:
            mt[0] = mt[N - 1]
            i = 1

    mt[0] = 0x80000000


def genrand_int32():
    global mti
    y = 0
    mag01 = [0x0, 0x9908b0df]

    if mti >= N:
        kk = 0

        if mti == N + 1:
            init_genrand(5489)

        for kk in range(kk, N - M):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1]
        kk += 1

        for kk in range(kk, N - 1, 1):
            y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
            mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1]
        y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
        mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1]
        mti = 0
    y = mt[mti]
    mti += 1
    y ^= (y >> 11)
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= (y >> 18)

    return y

Ở đây mình chỉ viết lại thuật toán để các bạn có thể dễ dàng hiểu được cách thức hoạt động của nó. Về cơ bản cách thức hoạt động của thuật toán này như sau:

  • Lần khỏi tạo đầu tiền chương trình sẽ cần 1 số gọi là seed dùng để sinh ra 1 bộ số ngẫu nhiên. Trong thực tế seed này sẽ được lấy từ urandom() nghĩa là các bit random được tổng hợp từ các trạng thái của hệ thống. Các bạn có thể gõ thử lệnh
cat /dev/urandom

để check thử.

  • Sau đó qua 1 vài bước biến đổi loằng ngoằng ta sẽ được 1 mảng gồm 624 phần tử.

  • Với mỗi phần tử này qua 1 bước biến đổi nữa ta sẽ cho ra 1 số random 32bit thông qua đoạn code:

    y = mt[mti]
    mti += 1
    y ^= (y >> 11)
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 15) & 0xefc60000
    y ^= (y >> 18)
    return y
    
  • Khi sử dụng hết 625 số này thì thuật toán sẽ dùng chính các số này để generate ra một mảng 625 phẩn tử khác

Cách thực hiện

  • Để tính được kết quả của hàm random này thì ta phải bắt buộc có được 625 số đã được sinh ra đó để ta có thể khôi phục lại được 625 phần tử của mảng mt Ở đây chúng ta để thực hiện việc khôi phục này thì ta không cần quan tâm cách mà thuật toán sinh ra mảng mt này. Chúng ta chỉ cần thực hiện để biển đổi lấy được mỗi phẩn tử của mảng mt ứng với số y (số random() trả về). Để ý kĩ đoạn code biến đổi này ta có thể thấy chúng dùng 1 chuỗi các phép dịch bít và phép XOR ^ để biến đổi phần tử mt[mt] thành kết quả y. Nhưng về cơ bản ở đây dùng 2 phép dịch bit trái và phải. Đối với phép dịch bít phải >> sau đó xor kết quả với số gốc thì phép biến đổi ngược lại bạn có thể để ý minh họa sau:

    y = 2999975253 # 0b10110010110011111111110101010101
    y>>18          #                   0b10110010110011
    y ^ (y>>18)    # 0b10110010110011111101000111100110
    
  • Nhắc lại chút cho bạn nào quên thì phép xor có một tính chất là A^B=C => C^B=A nhé 😄

  • Ta thấy rằng có (32-18) bít đầu tiên không bị thay đổi. Và 18 bit còn lại ta chỉ việc thực hiện phép XOR lần lượt các bit của y>>18 với kết quả là có thể thu được y. Đoạn code để thực hiện việc này như sau:

    def unshiftRight(x, shift):
        res = x
        for i in range(32):
            res = x ^ res >> shift
        return res
    
  • Trong trường hợp này shift chính là 18 còn res chính là 32 bit kết quả (y ^ (y>>18)

  • Ta đã giải quyết được phép xor với dịch bít phải. Còn phép xor với dịch bit trái cũng tương tự nhưng do còn thực hiện phép AND với Mask nên ta cần lấy shift & mask. Đoạn code thực hiện được mô tả như dưới đây:

    def unshiftLeft(x, shift, mask):
      res = x
      for i in range(32):
          res = x ^ (res << shift & mask)
      return res
    
  • Kết hợp 2 hàm trên ta thực hiện đảo ngược lại phép biến đổi:

    def untemper(v):
        v = unshiftRight(v, 18)
        v = unshiftLeft(v, 15, 0xefc60000)
        v = unshiftLeft(v, 7, 0x9d2c5680)
        v = unshiftRight(v, 11)
        return v
    
  • Giải quyết được phần trên thì bài toán của chúng ta đã trở lên đơn giản hơn rất nhiều. Bây giờ ta cần 1 hàm để generate ra kết quả nữa:

    def genrand_int32_fake(mt_fake):
       y = mt_fake
       y ^= (y >> 11)
       y ^= (y << 7) & 0x9d2c5680
       y ^= (y << 15) & 0xefc60000
       y ^= (y >> 18)
       return y
    

    Thử lại thành quả:

    Ta dùng đoạn chương trình sau để test lại xem thuật toán của chúng ta có đúng không nhé. Đây chỉ đơn giản là một đoạn chương trình sử dụng hàm random() default của python để test xem thuật toán của ta gen ra có chính xác không 😄 :

    import struct
    import random
    
    N = 624
    M = 397
    MATRIX_A = 0x9908b0df
    UPPER_MASK = 0x80000000
    LOWER_MASK = 0x7fffffff
    mt = [0 for i in range(624)]
    mti = N + 1
    
    
    def genrand_int32():
        global mti
        y = 0
        mag01 = [0x0, 0x9908b0df]
    
        if mti >= N:
            kk = 0
    
            for kk in range(kk, N - M):
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
                mt[kk] = mt[kk + M] ^ (y >> 1) ^ mag01[y & 0x1]
            kk += 1
    
            for kk in range(kk, N - 1, 1):
                y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
                mt[kk] = mt[kk + (M - N)] ^ (y >> 1) ^ mag01[y & 0x1]
            y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
            mt[N - 1] = mt[M - 1] ^ (y >> 1) ^ mag01[y & 0x1]
            mti = 0
        y = mt[mti]
        print(bin(y))
        mti += 1
        y ^= (y >> 11)
        y ^= (y << 7) & 0x9d2c5680
        y ^= (y << 15) & 0xefc60000
        y ^= (y >> 18)
    
        return y
    
    
    def unshiftRight(x, shift):
        res = x
        for i in range(32):
            res = x ^ res >> shift
        return res
    
    
    def unshiftLeft(x, shift, mask):
        res = x
        for i in range(32):
            res = x ^ (res << shift & mask)
        return res
    
    
    def untemper(v):
        v = unshiftRight(v, 18)
        v = unshiftLeft(v, 15, 0xefc60000)
        v = unshiftLeft(v, 7, 0x9d2c5680)
        v = unshiftRight(v, 11)
        return v
    
    
    for x in range(624):
        mt[x] = untemper(random.getrandbits(32))
    mti = 624
    
    print(genrand_int32())
    print(random.getrandbits(32))
    
  • Nếu 2 hàm print này ra kết quả giống nhau nghĩa là chương trình đã chạy đúng rồi đó.

Tổng kết

  • Chương trình này còn có thể áp dụng cho một số ngôn ngữ khác miễn là nó có sử dụng thuật toán MersenneTwister generator (MT19937) để sinh số ngẫu nhiên.
  • Đây là một bài toán khá hay, Đôi lúc cũng được ra trong các cuộc thi CTF.
  • Cám ơn các bạn đã đọc bài viết của mình 😄 Có gì thắc mắc hoặc có chỗ nào chưa ổn vui lòng để lại comment ạ!