Question

한자리수인 두 수 더하기 숏코딩 분석

C

오늘 재미있는 소스코드를 보게 되었다.
한자리인 두 수를 더한 결과를 출력하는 소스코드다.

1
2
3
4
5
6
7
8
9
#include <stdio.h>

int main(void) {
    int a;
    gets(&a);
    printf("%d\n", a % 85 - 43);
}
// input : 8 9
// output : 17

int변수에 gets로 입력받는건 둘째치고 도대체 어떻게 a % 85 - 43으로 두 수의 합이 나오는지 알아보기로 했다.

1. gets(&a)

먼저 gets(&a)를 했을 때, 입력이 a에 어떻게 들어가는지 알아보자.

gets는 원래 char * str를 인자로 받는 함수다. 하지만 지금은 &a즉, a 의 주소를 인자로 들어갔다.

1
char * gets ( char * str );

이 문제의 입력받는 input은 8 9\0(\0은 널문자) 널문자를 포함해서 총 4bytes다.
int타입의 크기가 4bytes인걸 감안했을때, 넘치지 않는 적당한 사이즈다.

그렇다면 값은 어떻게 들어갈까?

address &a &a + 1 &a + 2 &a + 3
char 8 9 \0
hex 38 20 39 00
dec 56 32 57 0

char형 배열의 값이 들어가는 것 처럼 앞에서부터 순서대로 들어간다.

2. a의 int값?

a에 들어간 값을 int로 읽으면 어떻게 될까?

a의 값을 읽어보기 전에 little endian에 대해서 간단히 집고 넘어가자면
int b = 0x12345678일때 b의 메모리를 보면 이렇게 생겼다.

address &b &b + 1 &b + 2 &b + 3
hex 78 56 34 12

12 34 56 78의 순서가 아니라는 점을 유의해야 한다.

그렇다면 a에 들어간 8 9\0의 int 값은 0x00392038인걸 알 수 있다.

이 값은 10진수로 다음과 같이 표현할 수 있다.

이 부분이 잘 이해가 되지 않는다면 2진수로 나눈것을 한번 봐보자.

1
2
             0 '\0'   57 '9'   32 ' '   56 '8'
0x00392038 = 00000000 00111001 00100000 00111000

256진법으로 생각했을때,

$57\times 256^2 + 32 \times 256 + 56$

뭐 위에나 아래나.. 사실 같은 이야기이긴 하다.

아무튼, 그러면 이제 저 식을 정리해 나가는 과정이 진행된다.

3. 식 정리

아래 식을 만족하는 N이 있다고 하자.
$256\equiv 1 \mod N$

그렇다면 mod N상에서 다음이 성립한다.
$57\times 256^2 + 32 \times 256 + 56$
$\equiv 57\times (256^2 \mod N) + 32 \times (256 \mod N) + 56$
$ \equiv 57\times 1 + 32 \times 1 + 56 \mod N$

일단, N의 값을 구해보자. 이때, N은 ‘9’의 아스키 코드인 57보다 커야한다.

1
2
3
4
5
6
7
i = ord('9')
while True:
  i += 1
  if 256 % i == 1:
    print(i)
    break
# 85

N이 될 수 있는 값 중, 가장 작은 값이 85라는 것을 알게 되었다.

$ 57 + 32 + 56 \mod 85$

여기에 ‘0’의 아스키 값이 48인것을 이용하여 분해하면,

$ 57\times 1 + 32 \times 1 + 56 \mod 85$
$= 9 + 8 + 32 + 48 + 48 \mod 85$
$= 9 + 8 + (32 + 48 + 48\mod 85) \mod 85$
$ = 9 + 8 + 43 \mod 85$

즉, 계산 결과 뒤에 추가적으로 붙는 43을 빼주면 8 + 9 = 17이라는 결과를 얻을 수 있다.

따라서 a - 43 mod 85즉, a % 85 - 43으로 계산이 가능해지는 것이다!

Share