이 문제는 주어진 해시의 충돌(두 입력이 같은 출력을 가지는 경우)을 찾는 문제입니다. 해시함수는 python 언어로 작성되었습니다.
def numerize(string: str) -> list[int]:
result = []
for char in string:
result.append(ord(char)-96)
return result
def hash(num_string: list[int]) -> int:
result = 0
for i in range(len(num_string)):
result += ((i+2) ** (num_string[i])) * 2
result -= (i+2) ** (num_string[::-1][i])
return (result) % 100000007
print(hash(numerize(input())))
numerize 함수는 전처리 함수이고, hash 함수가 메인입니다. 이 코드는 임의의 문자열을 받으면 numerize와 hash를 차례로 지나며 0 이상 100000007 미만의 정수를 출력합니다.
문제: 주어진 해시함수의 충돌을 찾는 코드와, 그 코드의 실행 결과로 str1, str2, hash_num 꼴의 출력(str1과 2는 충돌이 발생하는 문자열, hash_num은 충돌되는 해시값) 5개 이상을 제출하시오. 당연히 많이 제출할수록 좋은 답이 되겠습니다.
1개의 풀이가 있습니다.
Python 3.12
numerize 함수에서 ord(char) - 96 연산을 하므로, 유니코드 값이 96 미만인 경우 hash 함수에서 음(-)의 지수 연산으로 인해 반환 값이 float이 될 수 있음(Type hint에서는 int로 명시). 따라서, 유니코드 값 96 이상의 출력가능한 문자열만 입력되는 것으로 가정
import itertools
import string
def numerize(string: str) -> list[int]:
result = []
for char in string:
result.append(ord(char) - 96)
return result
def hash(num_string: list[int]) -> int:
result = 0
for i in range(len(num_string)):
result += ((i + 2) ** (num_string[i])) * 2
result -= (i + 2) ** (num_string[::-1][i])
return (result) % 100000007
def find_cases(assumelen=3):
# 유니코드 96 이상의 출력 가능한 문자열에 대해 길이 3인 문자열 순열 생성
pool = [
c for c in string.printable if (c not in string.whitespace) and (ord(c) >= 96)
]
teststrs = ("".join(c) for c in itertools.permutations(pool, assumelen))
testrst: dict[int, list[str]] = {} # key: hash => value: list[문자열]
for teststr in teststrs:
hashval = hash(numerize(teststr))
if hashval in testrst:
testrst[hashval].append(teststr)
else:
testrst[hashval] = [teststr]
# 충돌이 발생하는 문자열 선택
rst = sorted((k, v) for k, v in testrst.items() if len(v) > 1)
for k, v in rst:
print(f"{", ".join(v)}, {k}")
if __name__ == "__main__":
find_cases()
"""
bc`, de`, 20
bca, dea, 25
cd`, `ca, 34
adc, cea, 201
df`, `bd, 506
c`e, dga, 1969
bcf, def, 8147
bcg, deg, 32659
bch, deh, 130835
bci, dei, 523795
bcj, dej, 2096147
bck, dek, 8386579
pn`, ste, 9947047
bc}, de}, 14302797
bc|, de|, 19357996
bct, det, 22053065
bcy, dey, 22504863
bc~, de~, 30952878
bcl, del, 33550355
bcm, dem, 34209548
bcn, den, 36854512
bcr, der, 38681729
fpj, ~gd, 45138881
mnk, noh, 46077056
bco, deo, 47450752
bcs, des, 55251140
bcz, dez, 57128252
bcq, deq, 59604914
bc{, de{, 62730658
bcv, dev, 65431646
bcw, dew, 70115121
bcp, dep, 89868480
bcu, deu, 90309355
bcx, dex, 97237629
"""