这两天做了一个crypto的题，涉及到挺多的数学知识，还是非常的有意思，记录下解题的过程。 这个题，应该是2018 0ctf的PSN crypto的变种题。 和他们不一样的地方主要有一个，就是这题的4个sbox是不一样的。 解题中主要参看了以下文章： https://gist.github.com/ngg/f534e51c14a832d69c41289837078773 https://introspelliam.github.io/2018/04/03/crypto/%E7%BA%BF%E6%80%A7%E5%88%86%E6%9E%90%E6%B3%95/ https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
和0ctf不同的是，我们需要计算3个sbox的线性关系。 并且需要三轮ps执行后得到，p，c的的对应关系，进行最后一轮的key爆破，每次爆破两个字节。 可依此得到flag。 以下是手动执行三轮后得到的关系。
一开始没有太理解的地方是，以为p盒也是完全线性的，可以不用考虑，但其实不是，p,s都是要考虑计算。
from xx import *
import sympy
from numpy import *
import functools, binascii
#first step
print "sbox 1----------------------------"
sbox = [96, 236, 108, 63, 203, 20, 255, 199, 234, 140, 182, 95, 171, 116, 47, 167, 142, 143, 93, 130, 118, 181, 165, 122, 232, 49, 61, 226, 22, 201, 197, 251, 237, 13, 1, 168, 42, 245, 249, 38, 178, 109, 97, 213, 74, 219, 153, 70, 111, 176, 188, 253, 151, 99, 68, 155, 120, 208, 220, 3, 247, 40, 36, 215, 54, 28, 101, 207, 195, 6, 72, 55, 163, 124, 112, 217, 91, 132, 136, 87, 228, 161, 144, 117, 123, 89, 85, 138, 30, 193, 205, 18, 57, 67, 189, 106, 198, 33, 128, 46, 209, 5, 9, 214, 15, 157, 149, 78, 186, 173, 105, 29, 159, 210, 204, 235, 103, 184, 180, 131, 8, 73, 44, 243, 7, 216, 212, 11, 218, 160, 172, 115, 135, 88, 84, 139, 224, 192, 52, 19, 231, 147, 114, 113, 194, 141, 43, 206, 58, 254, 233, 32, 164, 125, 211, 174, 90, 133, 137, 86, 158, 65, 77, 146, 102, 185, 17, 48, 244, 134, 45, 16, 242, 238, 66, 10, 35, 252, 240, 56, 129, 4, 175, 230, 127, 156, 59, 79, 187, 100, 104, 183, 24, 126, 92, 53, 119, 190, 83, 229, 239, 39, 60, 227, 81, 200, 196, 27, 50, 31, 225, 62, 202, 21, 25, 241, 82, 80, 51, 26, 170, 12, 121, 166, 110, 177, 145, 98, 150, 222, 69, 154, 14, 64, 221, 2, 246, 41, 37, 250, 162, 34, 0, 223, 94, 169, 107, 23, 179, 248, 76, 191, 75, 148, 152, 71]
for insum in xrange(256):
for outsum in xrange(256):
if insum&(insum-1) and outsum&(outsum-1):
continue
bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
if abs(bias) > 40:
print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])
print "sbox 2----------------------------"
sbox = [127, 146, 172, 115, 135, 91, 84, 13, 31, 192, 204, 19, 231, 103, 203, 254, 194, 29, 17, 206, 18, 123, 245, 54, 139, 125, 113, 40, 138, 133, 137, 86, 158, 189, 77, 233, 102, 185, 181, 106, 227, 116, 8, 242, 6, 217, 213, 160, 35, 252, 235, 47, 219, 4, 238, 190, 67, 156, 144, 76, 23, 100, 104, 183, 143, 66, 92, 131, 119, 168, 164, 215, 239, 48, 39, 38, 44, 200, 196, 9, 50, 237, 225, 62, 202, 95, 25, 198, 82, 141, 129, 94, 170, 186, 121, 166, 110, 177, 187, 98, 73, 253, 69, 154, 162, 209, 70, 159, 12, 41, 37, 151, 211, 56, 230, 223, 43, 244, 248, 224, 179, 108, 96, 191, 75, 27, 152, 71, 51, 236, 126, 63, 36, 20, 24, 42, 52, 140, 109, 120, 171, 88, 45, 167, 10, 81, 80, 130, 118, 169, 165, 122, 21, 2, 61, 30, 22, 201, 197, 26, 210, 246, 1, 222, 250, 174, 249, 79, 178, 128, 97, 117, 74, 149, 153, 89, 111, 155, 34, 99, 221, 72, 68, 241, 15, 208, 220, 3, 247, 188, 33, 251, 90, 28, 16, 207, 59, 228, 195, 55, 163, 124, 112, 58, 148, 132, 136, 150, 240, 161, 173, 93, 134, 255, 85, 232, 83, 142, 205, 49, 199, 57, 53, 234, 0, 87, 14, 46, 218, 5, 193, 214, 229, 157, 60, 78, 114, 101, 105, 182, 65, 64, 226, 147, 243, 184, 180, 107, 175, 176, 145, 32, 7, 216, 212, 11]
for insum in xrange(256):
for outsum in xrange(256):
if insum&(insum-1) and outsum&(outsum-1):
continue
bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
if abs(bias) > 40:
print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])
print "sbox 3----------------------------"
sbox = [195, 28, 100, 124, 125, 61, 22, 55, 163, 47, 238, 175, 91, 101, 136, 87, 74, 161, 82, 132, 172, 157, 85, 138, 120, 193, 205, 18, 230, 57, 53, 166, 141, 185, 95, 69, 242, 5, 80, 214, 66, 16, 93, 99, 186, 77, 179, 182, 159, 64, 76, 107, 103, 184, 180, 78, 169, 32, 44, 119, 219, 147, 212, 11, 127, 228, 31, 105, 250, 88, 84, 139, 62, 192, 102, 162, 231, 56, 52, 73, 194, 68, 17, 178, 58, 229, 233, 200, 134, 156, 113, 223, 90, 190, 137, 86, 173, 65, 232, 146, 224, 234, 181, 106, 254, 33, 45, 129, 6, 9, 213, 10, 35, 252, 240, 115, 145, 4, 8, 215, 67, 225, 144, 79, 187, 218, 104, 183, 143, 34, 92, 131, 126, 168, 164, 123, 59, 135, 60, 227, 23, 46, 196, 83, 50, 29, 48, 201, 202, 216, 25, 198, 7, 206, 170, 94, 217, 117, 121, 160, 110, 114, 189, 98, 150, 19, 220, 154, 14, 209, 221, 27, 246, 41, 37, 243, 211, 12, 0, 158, 43, 244, 248, 39, 148, 207, 96, 191, 75, 239, 152, 71, 51, 236, 112, 63, 203, 20, 24, 21, 128, 140, 253, 255, 171, 116, 204, 167, 142, 81, 108, 130, 118, 235, 165, 122, 241, 49, 177, 226, 89, 2, 197, 26, 210, 13, 1, 222, 42, 245, 249, 38, 237, 109, 97, 133, 30, 149, 153, 70, 111, 176, 188, 199, 151, 72, 174, 155, 15, 208, 54, 3, 247, 40, 36, 251]
for insum in xrange(256):
for outsum in xrange(256):
if insum&(insum-1) and outsum&(outsum-1):
continue
bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
if abs(bias) > 40:
print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])
print "sbox 4----------------------------"
sbox = [100, 80, 162, 9, 119, 52, 164, 192, 209, 114, 60, 227, 23, 190, 196, 27, 76, 237, 11, 62, 88, 21, 25, 128, 82, 251, 139, 94, 250, 117, 121, 166, 168, 177, 189, 98, 150, 73, 69, 154, 14, 201, 221, 104, 200, 41, 96, 66, 211, 238, 0, 123, 58, 10, 248, 39, 179, 241, 170, 37, 75, 148, 152, 71, 131, 77, 172, 61, 203, 20, 231, 68, 223, 169, 43, 194, 47, 116, 120, 167, 142, 81, 93, 130, 118, 199, 51, 122, 83, 67, 140, 226, 8, 236, 197, 149, 210, 13, 1, 222, 42, 245, 249, 38, 178, 109, 97, 165, 74, 86, 153, 70, 111, 91, 188, 99, 151, 72, 198, 205, 15, 208, 26, 3, 247, 40, 36, 163, 195, 28, 191, 207, 59, 228, 232, 55, 171, 176, 112, 224, 50, 132, 136, 87, 49, 161, 173, 214, 134, 89, 85, 138, 30, 193, 129, 18, 230, 57, 53, 110, 34, 253, 46, 143, 218, 5, 225, 234, 181, 157, 145, 78, 186, 101, 105, 182, 159, 64, 108, 147, 103, 184, 246, 107, 255, 32, 44, 243, 219, 124, 212, 90, 127, 160, 16, 115, 135, 239, 84, 229, 31, 144, 204, 19, 24, 56, 180, 235, 2, 29, 17, 206, 202, 156, 233, 54, 22, 125, 113, 174, 35, 133, 137, 4, 158, 92, 126, 146, 102, 185, 63, 106, 254, 33, 45, 242, 6, 217, 213, 95, 48, 252, 240, 12, 155, 216, 7, 215, 65, 175, 244, 79, 187, 220, 141, 183]
for insum in xrange(256):
for outsum in xrange(256):
if insum&(insum-1) and outsum&(outsum-1):
continue
bias = sum((bin(x&insum).count('1') + bin(sbox[x]&outsum).count('1')) % 2 for x in xrange(256)) - 128
if abs(bias) > 40:
print '+'.join(['X'+str(i) for i in xrange(8) if insum&(2**i)] + ['Y'+str(i) for i in xrange(8) if outsum&(2**i)])
# sbox 1----------------------------
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X0+X1+Y1
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X0+X1+X4+X5+Y0
# X6+Y0+Y2+Y3+Y7
# X0+X1+X2+X4+X6+Y4
# X0+X1+X2+X4+X5+X6+Y7
# X2+X3+X4+X5+X6+Y5
# X7+Y0+Y4+Y5+Y6+Y7
# X0+X4+X7+Y2
# X0+X2+X4+X7+Y3
# X0+X1+X2+X3+X5+X6+X7+Y6
# sbox 2----------------------------
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X0+X1+Y1
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X0+X1+X4+X5+Y0
# X6+Y0+Y2+Y3+Y7
# X0+X1+X2+X4+X6+Y4
# X0+X1+X2+X4+X5+X6+Y7
# X2+X3+X4+X5+X6+Y5
# X7+Y0+Y4+Y5+Y6+Y7
# X0+X4+X7+Y2
# X0+X2+X4+X7+Y3
# X0+X1+X2+X3+X5+X6+X7+Y6
# sbox 3----------------------------
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X0+X1+Y1
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X0+X1+X4+X5+Y0
# X6+Y0+Y2+Y3+Y7
# X0+X1+X2+X4+X6+Y4
# X0+X1+X2+X4+X5+X6+Y7
# X2+X3+X4+X5+X6+Y5
# X7+Y2+Y3+Y4+Y5+Y6
# X0+X1+X2+X3+X5+X7+Y6
# X0+X4+X6+X7+Y2
# X0+X2+X4+X6+X7+Y3
# sbox 4----------------------------
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X0+X1+Y1
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X0+X1+X4+X5+Y0
# X6+Y0+Y2+Y3+Y7
# X0+X1+X2+X4+X6+Y4
# X0+X1+X2+X4+X5+X6+Y7
# X2+X3+X4+X5+X6+Y5
# X7+Y2+Y3+Y4+Y5+Y6
# X0+X1+X2+X3+X5+X7+Y6
# X0+X4+X6+X7+Y2
# X0+X2+X4+X6+X7+Y3
# sbox1 same as sbox2
# sbox3 same as sbox4
# second step
# Some precomputations of the P-box to use (byte,bit) indexing
#sbox1 sbox2
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X0+X1+Y1
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X0+X1+X4+X5+Y0
# X6+Y0+Y2+Y3+Y7
# X0+X1+X2+X4+X6+Y4
# X0+X1+X2+X4+X5+X6+Y7
# X2+X3+X4+X5+X6+Y5
# X7+Y0+Y4+Y5+Y6+Y7
# X0+X4+X7+Y2
# X0+X2+X4+X7+Y3
# X0+X1+X2+X3+X5+X6+X7+Y6
# sbox 1-4 same ====>
# X0+Y1+Y2+Y5+Y6
# X1+Y2+Y5+Y6
# X2+Y2+Y3
# X3+Y1+Y5+Y7
# X4+Y0+Y1+Y4+Y7
# X5+Y4+Y7
# X6+Y0+Y2+Y3+Y7
# X7+Y0+Y4+Y5+Y6+Y7
pt = [[None for i in xrange(8)] for j in xrange(8)]
for i in xrange(8):
for j in xrange(8):
c = bytearray('\0'*8)
c[i] = chr(2**j)
d = permutation(c)
i2 = None
for k in xrange(8):
if d[k] != 0:
assert i2 is None
i2 = k
j2 = None
for k in xrange(8):
if (d[i2]&(2**k)) != 0:
assert j2 is None
j2 = k
pt[i][j] = (i2,j2)
K = sympy.IndexedBase('K')
P = sympy.IndexedBase('P')
U4 = sympy.IndexedBase('U4')
def k(i, j, b):
# not interested in which key bits are involved
return 0
def p(i, b):
# plain-text bits
return P[i, b]
def u(i, j, b):
if i == 4:
# this is the input of the last S-box, leave it as it is
return U4[j, b]
# These numbers are from the S-box biases where there is only a single input bit involved, map them to output bits
return sum(map(lambda x: v(i, j, x), [[1,2,5,6], [2,5,6], [2,3], [1,5,7], [0,1,4,7], [4,7], [0,2,3,7], [0,4,5,6,7]][b]))
def v(i, j, b):
# From the output of an S-box we can get to the input of the next S-box by using the permutations (and some key bits)
return k(i+1, pt[j][b][0], pt[j][b][1])+u(i+1, pt[j][b][0], pt[j][b][1])
def x(i):
# Input of the first S-box is the plaintext bit ^ a key bit
return p(0, i)+k(1, 0, i)
def y(i):
# Output of the first S-box
return v(1, 0, i)
#sbox 1=====>
# X0+X1+X4+X5+Y0
# X0+X1+Y1
# X0+X4+X7+Y2
# X0+X2+X4+X7+Y3
# X0+X1+X2+X4+X6+Y4
# X2+X3+X4+X5+X6+Y5
# X0+X1+X2+X3+X5+X6+X7+Y6
# X0+X1+X2+X4+X5+X6+Y7
print "round 1 s box"
#print x(0)+x(1)+x(4)+x(5)+y(0)
print x(0)+x(1)+y(1)
# print x(0)+x(4)+x(7)+y(2)
# print x(0)+x(2)+x(4)+x(7)+y(3)
# print x(0)+x(1)+x(2)+x(4)+x(6)+y(4)
# print x(2)+x(3)+x(4)+x(5)+x(6)+y(5)
# print x(0)+x(1)+x(2)+x(3)+x(5)+x(6)+x(7)+y(6)
# print x(0)+x(1)+x(2)+x(4)+x(5)+x(6)+y(7)
# P[0, 0] + P[0, 1] + P[0, 4] + P[0, 5] + U4[0, 3] + U4[2, 0] + U4[3, 4] + U4[4, 0] + U4[6, 3] + U4[7, 2] + U4[7, 4]
# P[0, 0] + P[0, 1] + U4[2, 6] + U4[3, 1] + U4[3, 7] + 2*U4[6, 7]
# P[0, 0] + P[0, 4] + P[0, 7] + U4[0, 0] + U4[0, 1] + U4[0, 2] + U4[2, 5] + U4[3, 2] + U4[4, 1] + U4[4, 7] + U4[6, 0]
# P[0, 0] + P[0, 2] + P[0, 4] + P[0, 7] + U4[0, 2] + U4[0, 6] + U4[2, 1] + U4[3, 0] + U4[3, 2] + U4[5, 4] + U4[7, 6]
# P[0, 0] + P[0, 1] + P[0, 2] + P[0, 4] + P[0, 6] + U4[0, 3] + U4[5, 3] + U4[6, 4] + U4[6, 7] + U4[7, 0] + U4[7, 2]
# P[0, 2] + P[0, 3] + P[0, 4] + P[0, 5] + P[0, 6] + U4[0, 1] + U4[0, 2] + U4[1, 0] + U4[1, 1] + U4[2, 2] + U4[2, 4] + U4[4, 4] + U4[4, 6] + U4[5, 6] + U4[6, 0] + U4[6, 1] + U4[6, 3]
# P[0, 0] + P[0, 1] + P[0, 2] + P[0, 3] + P[0, 5] + P[0, 6] + P[0, 7] + U4[0, 0] + 2*U4[0, 1] + 2*U4[0, 2] + U4[2, 2] + U4[2, 5] + U4[3, 2] + U4[4, 1] + U4[4, 4] + U4[4, 6] + U4[4, 7] + U4[6, 0]
# P[0, 0] + P[0, 1] + P[0, 2] + P[0, 4] + P[0, 5] + P[0, 6] + U4[0, 0] + U4[0, 4] + U4[2, 3] + U4[2, 6] + U4[3, 1] + U4[3, 2] + U4[3, 4] + U4[3, 7] + U4[4, 2] + U4[4, 6] + 2*U4[6, 7] + U4[7, 4]
#after round 1
# X0+X1+Y1
## P[0, 0] + P[0, 1] + U4[2, 6] + U4[3, 1] + U4[3, 7] + 2*U4[6, 7]
## P[0, 0] + P[0, 1] + U4[2, 6] + U4[3, 1] + U4[3, 7]
print "round 1 p box"
block = bytearray("\x02\x00\x00\x00\x00\x00\x00\x00")
tmp = permutation(block)
tmp = s2b(tmp)
for i in xrange(0,8):
for j in xrange(0,8):
if tmp[8*i+j] == 1:
print "hint!----"
print i + 1
print j + 1
# hint!----
# 5
# 3
# \x00\x00\x00\x00\x20\x00\x00\x00
#x(5)
#round 2 s box
print "round 2 s box"
## X5+Y4+Y7
# \x00\x00\x00\x00\x90\x00\x00\x00
#P[0, 5] + U4[0, 0] + U4[0, 3] + U4[0, 4] + U4[2, 3] + U4[2, 6] + U4[3, 1] + U4[3, 2] + U4[3, 4] + U4[3, 7] + U4[4, 2] + U4[4, 6] + U4[5, 3] + U4[6, 4] + 3*U4[6, 7] + U4[7, 0] + U4[7, 2] + U4[7, 4]
#round 2 p box
print "round 2 y4 p box"
block = bytearray("\x00\x00\x00\x00\x90\x00\x00\x00")
tmp = permutation(block)
tmp = s2b(tmp)
for i in xrange(0,8):
for j in xrange(0,8):
if tmp[8*i+j] == 1:
print "hint!----"
print i + 1
print j + 1
# hint!----
# 7
# 3
# hint!----
# 7
# 5
# \x00\x00\x00\x00\x00\x00\x28\x00
# x(3)+x(5)
print "round 3 s box"
## x(3)+x(5)
# X3+Y1+Y5+Y7
# X5+Y4+Y7
# x(3)+x(5) ==> y(1)+y(4)+y(5)
# should find max x(3)+x(5) in sbox, The above method may not be right
# result is same in this case
# \x00\x00\x00\x00\x00\x00\x32\x00
print "round 3 p box"
block = bytearray("\x00\x00\x00\x00\x00\x00\x32\x00")
tmp = permutation(block)
tmp = s2b(tmp)
for i in xrange(0,8):
for j in xrange(0,8):
if tmp[8*i+j] == 1:
print "hint!----"
print i + 1
print j + 1
# hint!----
# 3
# 2
# hint!----
# 4
# 1
# hint!----
# 4
# 7
# \x00\x00\x40\x82\x00\x00\x00\x00
# p[0,0],p[0,1] -> c[2,6], c[3,7],c[3,1]
以下是根据该线性关系爆破两字节脚本
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
int sbox_inv[256] = {
50, 98, 208, 123, 223, 165, 236, 246, 92, 3, 53, 18, 243, 97, 40, 120, 194, 210,
155, 203, 69, 21, 216, 12, 204, 22, 122, 15, 129, 209, 152, 200, 185, 233, 160,
220, 126, 59, 103, 55, 125, 45, 100, 74, 186, 234, 162, 76, 240, 144, 140, 86,
5, 158, 215, 135, 205, 157, 52, 132, 10, 67, 19, 230, 177, 248, 47, 89, 71, 38,
111, 63, 117, 37, 108, 60, 16, 65, 171, 251, 1, 81, 24, 88, 198, 150, 109, 143,
20, 149, 191, 113, 225, 82, 27, 239, 46, 106, 35, 115, 0, 173, 228, 180, 43, 174,
231, 183, 178, 105, 159, 112, 138, 218, 9, 195, 77, 29, 84, 4, 78, 30, 87, 51,
189, 217, 226, 192, 23, 154, 83, 64, 141, 221, 148, 196, 142, 222, 151, 26, 90,
254, 80, 163, 201, 170, 227, 179, 61, 95, 36, 116, 62, 110, 39, 244, 213, 169,
224, 176, 193, 145, 2, 127, 6, 107, 31, 79, 32, 73, 58, 136, 66, 146, 219, 249,
137, 33, 104, 56, 206, 168, 175, 255, 181, 229, 172, 252, 114, 34, 13, 130, 7,
153, 75, 128, 14, 94, 118, 85, 44, 41, 212, 68, 202, 119, 211, 131, 121, 8, 96,
48, 190, 238, 147, 247, 245, 237, 164, 188, 253, 42, 99, 72, 139, 166, 91, 11, 133,
199, 156, 70, 134, 214, 167, 207, 93, 17, 49, 197, 242, 57, 235, 187, 250, 101,
182, 124, 54, 102, 28, 25, 241, 161, 232, 184};
int cnt[256][256];
int bit(int n, int k)
{
return (n & (1 << k)) != 0;
}
int main()
{
auto f = fopen("data", "rb");
for (int i = 0; i < 65536; i++) {
uint8_t p[8], c[8];
fread(&p, 8, 1, f);
fread(&c, 8, 1, f);
for (int a = 0; a < 256; a++) {
for (int b = 0; b < 256; b++) {
int u4b0 = sbox_inv[(int)c[2] ^ a], u4b6 = sbox_inv[(int)c[3] ^ b];
if (bit(p[0], 0) ^ bit(p[0], 1) ^ bit(u4b0, 6) ^ bit(u4b6, 7) ^ bit(u4b6, 1)) {
cnt[a][b]++;
}
}
}
}
for (int a = 0; a < 256; a++) {
for (int b = 0; b < 256; b++) {
int bias = abs(cnt[a][b] - 32768);
if (bias > 18200)
cout << a << " " << b << " " << bias << endl;
}
}
}
// 4 51 18217
// 15 51 18213
// 43 51 18239
// 47 51 18202
// 48 51 18316
// 52 51 18369
// 61 51 18230
// 68 51 18203
// 95 40 18297
// 95 50 18298
// 95 51 19877 hint
// 95 88 18229
// 95 89 18242
// 95 98 18208
// 95 138 18299
// 95 183 18353
// 142 51 18269
// 148 51 18229
// 180 51 18213
// 213 51 18220
// 216 51 18329
// 219 51 18514
// 232 51 18239
// 236 51 18208