CRC

文字列を多項式に移してmodをとったやつ。何故か処理の前後でbit反転する。

def crc32(crc, data):
    crc = 0xFFFFFFFF ^ crc
    for c in data:
        crc = crc ^ ord(c)
        for i in range(8):
            crc = (crc >> 1) ^ (0xEDB88320 * (crc & 1))
    return 0xFFFFFFFF ^ crc

PR.<x> = PolynomialRing(GF(2))
QR.<x> = PR.quotient(x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1)

def crc32(data):
    crc = sum(x^i for i in range(32))
    for c in data:
        for i in range(8):
            if ord(c) & (1 << i):
                crc += x ^ (32 - i - 1)
        crc *= x ^ 8
    return crc

def crc32_tonum(poly):
    return sum((2 ^ i) * int(1 - v) for i, v in enumerate(reversed(poly.list())))
print(crc32_tonum(crc32("TSG")))

def i2p(F, x):
    return F(Integer(x).bits())

def p2i(p):
    return Integer(p.list(), 2)

def rev(F, p, size):
    return F((p.list() + [0] * size)[:size][::-1])

def crc(n, g, mask, reverse, init, data):
    F = g.parent()
    x = F.gen()
    k = len(data) * 8
    W = i2p(F, int.from_bytes(data, "little"))
    M = i2p(F, mask)
    I = i2p(F, init)
    if reverse:
        W = rev(F, W, k)
        M = rev(F, M, n)
        I = rev(F, I, n)
    value = (W*x^n + (M + I)*x^k + M) % g
    if reverse:
        value = rev(F, value, n)
    return p2i(value)


from zlib import crc32
message = b"world"
message2 = b"hello"
checksum = crc32(message)
checksum2 = crc32(message2, checksum)
print(checksum)
print(checksum2)
print(crc32(message +message2))

PR.<x> = PolynomialRing(GF(2))
# 生成多項式
g = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1
c = crc(32, g, 0xffffffff, True, 0, message)
c2 = crc(32, g, 0xffffffff, True, c, message2)
c3 = crc(32, g, 0xffffffff, True, 0, message + message2)
print(c)
print(c2)
print(c3)

Properties

（ただし繰り上がりなし）

Combine

と、がわかる時、がわかるというもの。Zlibにcrc32_combineという名前で存在している。

def crc32_combine(crc1, crc2, len2):
    """Explanation algorithm: https://stackoverflow.com/a/23126768/654160
    crc32(crc32(0, seq1, len1), seq2, len2) == crc32_combine(
        crc32(0, seq1, len1), crc32(0, seq2, len2), len2)"""
    # degenerate case (also disallow negative lengths)
    if len2 <= 0:
        return crc1

    # put operator for one zero bit in odd
    # CRC-32 polynomial, 1, 2, 4, 8, ..., 1073741824
    odd = [0xEDB88320] + [1 << i for i in range(0, 31)]
    even = [0] * 32

    def matrix_times(matrix, vector):
        number_sum = 0
        matrix_index = 0
        while vector != 0:
            if vector & 1:
                number_sum ^= matrix[matrix_index]
            vector = vector >> 1 & 0x7FFFFFFF
            matrix_index += 1
        return number_sum

    # put operator for two zero bits in even - gf2_matrix_square(even, odd)
    even[:] = [matrix_times(odd, odd[n]) for n in range(0, 32)]

    # put operator for four zero bits in odd
    odd[:] = [matrix_times(even, even[n]) for n in range(0, 32)]

    # apply len2 zeros to crc1 (first square will put the operator for one
    # zero byte, eight zero bits, in even)
    while len2 != 0:
        # apply zeros operator for this bit of len2
        even[:] = [matrix_times(odd, odd[n]) for n in range(0, 32)]
        if len2 & 1:
            crc1 = matrix_times(even, crc1)
        len2 >>= 1

        # if no more bits set, then done
        if len2 == 0:
            break

        # another iteration of the loop with odd and even swapped
        odd[:] = [matrix_times(even, even[n]) for n in range(0, 32)]
        if len2 & 1:
            crc1 = matrix_times(odd, crc1)
        len2 >>= 1

        # if no more bits set, then done
    # return combined crc
    crc1 ^= crc2
    return crc1

多項式

こんな感じで多項式環を作る

PR.<x> = PolynomialRing(GF(2))

多項式

g = x^32 + x^26 + x^23 + x^22 + x^16 + x^12+x^11+x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

係数

g.coefficients(sparse=0)

の逆数

(x^32).inverse_mod(g)

便利グッズ

def i2p(F, x):
    return F(Integer(x).bits())

def p2i(p):
    return Integer(p.list(), 2)

def rev(F, p, size):
    return F((p.list() + [0] * size)[:size][::-1])

def crc(n, g, mask, reverse, init, data):
    F = g.parent()
    x = F.gen()
    k = len(data) * 8
    W = i2p(F, int.from_bytes(data, "little"))
    M = i2p(F, mask)
    I = i2p(F, init)
    if reverse:
        W = rev(F, W, k)
        M = rev(F, M, n)
        I = rev(F, I, n)
    value = (W*x^n + (M + I)*x^k + M) % g
    if reverse:
        value = rev(F, value, n)
    return p2i(value)


def crc_forgery_append(n, g, mask, reverse, init, desired):
    """
    find data which satysfies crc(data, init) == desired
    the bit length of data is n
    """
    F = g.parent()
    x = F.gen()
    D = i2p(F, desired)

    M = i2p(F, mask)
    I = i2p(F, init)
    if reverse:
        D = rev(F, D, n)
        M = rev(F, M, n)
        I = rev(F, I, n)

    xninv = inverse_mod(x^n, g)
    W = ((D - M - (M+I)*x^n)*xninv) % g
    if reverse:
        W = rev(F, W, n)
    return int(p2i(W)).to_bytes((n + 7) // 8, 'little')

def crc_combine(n, g, mask, reverse, init, checksum_a, checksum_b, len_b):
    """
    calc crc(A || B) from crc(A), crc(B), and len(B)
    checksum_a: crc(A, init)
    checksum_b: crc(B, init)
    datalen: len(B) (bytesize)
    """

    F = g.parent()
    len_b = len_b * 8
    I = i2p(F, init)
    S = i2p(F, checksum_b)
    newI = i2p(F, checksum_a)
    if reverse:
        I = rev(F, I, n)
        S = rev(F, S, n)
        newI = rev(F, newI, n)

    newS = (S - I*x^len_b + newI*x^len_b) % g
    if reverse:
        newS = rev(F, newS, n)

    return int(p2i(newS))


def crc_prefix_checksum(n, g, mask, reverse, init, data, value):
    """
    calculate crc(prefix) when crc(prefix + data) == value
    and the prefix is unknown
    """
    F = g.parent()
    x = F.gen()
    D = i2p(F, value)

    l = len(data) * 8
    W = i2p(F, int.from_bytes(data, "little"))
    M = i2p(F, mask)
    if reverse:
        D = rev(F, D, n)
        W = rev(F, W, l)
        M = rev(F, M, n)

    xlinv = inverse_mod(x^l, g)
    I = ((D - M - W*x^n)*xlinv + M) % g
    if reverse:
        I = rev(F, I, n)

    return p2i(I)

def crc_postfix_checksum(n, g, mask, reverse, init, checksum_a, checksum, postfix_len):
    """
    calculate crc(postfix) when crc(data + postfix, init) == value
    and the postfix is k-byte unknown
    checksum_a: crc(data, init)
    checksum: crc(data + postfix, init)
    postfix_len: len(postfix)

    (this is the inverse operation of crc_combine)
    """
    return crc_combine(n, g, mask, reverse, checksum_a, init, checksum, postfix_len)

def crc_forgery_prepend(n, g, mask, reverse, init, data, desired):
    """
    find prefix which satysfies crc(prefix + data) == desired
    it is equivalent to find checksum of prefix which satysfies crc(data, prefix) == desired, and regenerate the byte squence, which is prefix, from desired
    """
    I = crc_prefix_checksum(n, g, mask, reverse, init, data, desired)
    return crc_forgery_append(n, g, mask, reverse, init, p2i(I))

def crc_forgery_insert(n, g, mask, reverse, init, prefix, postfix, desired):
    value = crc(n, g, mask, reverse, init, prefix)
    return crc_forgery_prepend(n, g, mask, reverse, value, postfix, desired)


if __name__ == "__main__":
    import unittest
    from zlib import crc32, adler32

    PR.<x> = GF(2)[]
    g = x^32 + x^26 + x^23 + x^22 + x^16 + x^12 + x^11 + x^10 + x^8 + x^7 + x^5 + x^4 + x^2 + x + 1

    class TestCRC32(unittest.TestCase):
        def test_helloworld(self):
            message = b"hello world"
            self.assertEqual(crc32(message), crc(32, g, 0xffffffff, True, 0, message))

        def test_hello_world(self):
            message1 = b"hello"
            checksum1 = crc32(message1)
            checksum1_ = crc(32, g, 0xffffffff, True, 0, message1)
            self.assertEqual(checksum1, checksum1_)

            message2 = b"world"
            checksum2 = crc32(message2, checksum1)
            checksum2_ = crc(32, g, 0xffffffff, True, checksum1_, message2)
            self.assertEqual(checksum2, checksum2_)

        def test_randomstring(self):
            import random
            import string

            message = "".join(random.choices(string.ascii_letters, k=30)).encode()
            self.assertEqual(crc32(message), crc(32, g, 0xffffffff, True, 0, message))

    class TestCRC64(unittest.TestCase):
        def test_crc64(self):
            g = x^64 + x^4 + x^3 + x + 1  # CRC-64-ISO
            message = b"hello world"
            checksum = int(crc(64, g, 0, True, 0, message))
            self.assertEqual(crc(64, g, 0, True, 0, message + checksum.to_bytes(8, "little")), 0)

        def test_randomstring(self):
            import random
            import string
            g = x^64 + x^4 + x^3 + x + 1  # CRC-64-ISO

            message = "".join(random.choices(string.ascii_letters, k=30)).encode()
            checksum = int(crc(64, g, 0, True, 0, message))
            self.assertEqual(crc(64, g, 0, True, 0, message + checksum.to_bytes(8, "little")), 0)

    class TestCRCForgery(unittest.TestCase):
        def test_append(self):
            message = b"hello world"
            checksum = crc32(message)
            forgery = crc_forgery_append(32, g, 0xffffffff, True, checksum, 0)
            self.assertEqual(len(forgery), 4)
            self.assertEqual(crc32(message + forgery), 0)

        def test_append_arbitrary(self):
            import random
            import string
            message = "".join(random.choices(string.ascii_letters, k=30)).encode()
            desired = random.getrandbits(32)
            checksum = crc32(message)
            forgery = crc_forgery_append(32, g, 0xffffffff, True, checksum, desired)
            self.assertEqual(crc32(message + forgery), desired)

        def test_prepend(self):
            message = b"hello world"
            forgery = crc_forgery_prepend(32, g, 0xffffffff, True, 0, message, 0)
            self.assertEqual(len(forgery), 4)
            self.assertEqual(crc32(forgery + message), 0)

        def test_prepend_arbitrary(self):
            import random
            import string
            message = "".join(random.choices(string.ascii_letters, k=30)).encode()
            desired = random.getrandbits(32)
            forgery = crc_forgery_prepend(32, g, 0xffffffff, True, 0, message, desired)
            self.assertEqual(len(forgery), 4)
            self.assertEqual(crc32(forgery + message), desired)

        def test_insert(self):
            message1 = b"hello "
            message2 = b" world"
            forgery = crc_forgery_insert(32, g, 0xffffffff, True, 0, message1, message2, 0)
            self.assertEqual(len(forgery), 4)
            self.assertEqual(crc32(message1 + forgery + message2), 0)

        def test_crc64_insert(self):
            import random
            import string
            g = x^64 + x^4 + x^3 + x + 1  # CRC-64-ISO

            message1 = "".join(random.choices(string.ascii_letters, k=30)).encode()
            message2 = "".join(random.choices(string.ascii_letters, k=30)).encode()
            desired = random.getrandbits(64)
            forgery = crc_forgery_insert(64, g, 0, True, 0, message1, message2, desired)

            self.assertEqual(crc(64, g, 0, True, 0, message1 + forgery + message2), desired)

        def test_crc_combine(self):
            message1 = b"hello "
            message2 = b"world"

            checksum1 = crc32(message1)
            checksum2 = crc32(message2)
            combined_checksum = crc_combine(32, g, 0xffffffff, True, 0, checksum1, checksum2, len(message2))

            self.assertEqual(crc32(message1 + message2), combined_checksum)

        def test_crc_combine_random_init(self):
            import random
            init = random.getrandbits(32)
            message1 = b"hello "
            message2 = b"world"

            checksum1 = crc(32, g, 0xffffffff, True, init, message1)
            checksum2 = crc(32, g, 0xffffffff, True, init, message2)
            combined_checksum = crc_combine(32, g, 0xffffffff, True, init, checksum1, checksum2, len(message2))

            self.assertEqual(crc(32, g, 0xffffffff, True, init, message1 + message2), combined_checksum)

        def test_crc_prefix(self):
            prefix = b"hello "
            message = b"world"

            value = crc32(prefix + message)
            value_of_prefix = crc_prefix_checksum(32, g, 0xffffffff, True, 0, message, value)
            self.assertEqual(crc32(prefix), value_of_prefix)

        def test_crc_postfix(self):
            message = b"hello "
            postfix = b"world"

            checksum = crc32(message + postfix)
            checksum_of_message = crc32(message)
            checksum_of_postfix = crc_postfix_checksum(32, g, 0xffffffff, True, 0, checksum_of_message, checksum, len(postfix))
            self.assertEqual(crc32(postfix), checksum_of_postfix)

        def test_crc_insert_with_unknown_postfix(self):
            import random
            message = b"hello"
            postfix_len = 4
            unknown_postfix = random.getrandbits(postfix_len * 8).to_bytes(postfix_len, "little")
            desired_checksum = 0

            checksum = crc32(message + unknown_postfix)
            postfix_checksum = crc_postfix_checksum(32, g, 0xffffffff, True, 0, crc32(message), checksum, postfix_len)
            dummy_postfix = crc_forgery_append(32, g, 0xffffffff, True, 0, postfix_checksum)
            forgery = crc_forgery_insert(32, g, 0xffffffff, True, 0, message, dummy_postfix, desired_checksum)
            self.assertEqual(crc32(message + forgery + unknown_postfix), desired_checksum)

    unittest.main()

CRCのための生成多項式を作るやつ

PR.<x> = GF(2)[]
while True:
    g = PR.random_element(128)
    if g.is_irreducible() and g.is_primitive():
        break

# 先頭の1bitを落として順序を反転
g_reversed = Integer(g.list()[:-1][::-1], 2)
print(hex(g_reversed))