BOJ 10930 - python
10930
- 문제유형 : 해시, 구현
- sha256 알고리즘만 사용하면 간단하게 해결 가능 -> 검색 ㄱ
- 알고리즘을 직접 만들라는 얘기는 아니고 그냥 python 라이브러리 사용하면 된다.
문제풀이
sha256알고리즘은 크게 두 단계로 나뉜다. => 해시 대상 메시지를 전처리하는 단계, 전처리된 메시지를 바탕으로 해시를 계산하는 단계
- 해시 대상 메시지를 전처리하는 단계
- 메시지 : SHA-256을 적용해야하는 데이터
- 메시지 bit 의 길이가 512의 배수가 되도록 padding 을 추가하는 것이 전처리 단계에서 수행하는 작업
- 원본 메시지의 바로 뒤에 비트 ‘1’ 을 하나 추가한다.
- 메시지의 길이가 512의 배수가 되도록 메시지에 0을 추가한다.
- 메시지의 마지막 64bit에는 원본 메시지의 bit 길이를 적는다.
- 전처리된 메시지 해싱
- 메시지 전처리가 끝났다면 메시지의 bit 길이는 512의 배수 형태가 된다.
- 이러한 전처리된 메시지를 512bit 단위로 쪼개서 여러 개의 chunk 를 만든다.
- 그리고 이러한 chunk 들을 차례대로 순회하면서 특정 연산을 수행하여 최종적인 hash 값을 계산한다.
일단 기본적인 원리는 위와같고, 나는 파이썬 라이브러리로 풀 거니까 더 자세한 알고리즘 원리는 출처를 남겨놓을테니 그 분이 설명하신 거 보면 이해가 잘 될 것이다. 사실 완벽히 이해가 되는 건 아니다. 아마 디논설 공부가 부족한가보다.
import hashlib //해시라이브러리 임포트
a = input() //input을 받아줄 변수 생성
hash_a = hashlib.sha256(str(a).encode('utf-8'))
//input을 문자열화해서 sha256알고리즘을 적용해주고 utf-8로 인코딩해준 후
print(hash_a.hexdigest())
//출력! hexdigest()는 몰라서 서치했다.
//-> sha256 해시 객체를 hexdigest로 digest 요청한 것을 출력하라는 말
- 해시(hash)의 유형마다 이름이 지정된 생성자 메서드가 있습니다. 모두 같은 간단한 인터페이스를 갖는 해시 객체를 반환합니다.
- 예를 들어: SHA-256 해시 객체를 만들려면 sha256()을 사용하십시오. 이제 update() 메서드를 사용하여 이 객체에 바이트열류 객체(보통 bytes)를 공급할 수 있습니다.
- 언제든지 digest()나 hexdigest() 메서드를 사용하여 지금까지 공급된 데이터의 연결에 대한 요약(digest)을 요청할 수 있습니다.
문제 풀이 핵심 아이디어
- hashlib의 sha256함수를 이용하면 SHA 256 해시를 구할 수 있다.
- hashlib.sha256(문자열의 바이트 객체).hexdigest() : 해시 결과 문자열
나동빈T 소스코드
import hashlib
input_data = input()
encoded_data = input_data.encode()
result = hashlib.sha256(encoded_data).hexdigest()
print(result)
sha256 : SHA(Secure Hash Algorithm) 알고리즘의 한 종류
- SHA(Secure Hash Algorithm, 안전한 해시 알고리즘) 함수들은 서로 관련된 암호학적 해시 함수들의 모음이다. 256비트로 구성되며 64자리 문자열을 반환한다.
- SHA-256은 미국의 국립표준기술연구소(NIST; National Institute of Standards and Technology)에 의해 공표된 표준 해시 알고리즘인 SHA-2 계열 중 하나이며 블록체인에서 가장 많이 채택하여 사용하고 있다. 이름에 내포되어 있듯 2의 256승만큼 경우의 수를 만들수 있다.
- 개인용 컴퓨터로 무차별 대입을 수행해 해시 충돌 사례를 찾으려고 할 때 많은 시간이 소요될 정도로 큰 숫자이므로 충돌로부터 비교적 안전하다고 평가된다.