전체 글
-
[정수론] 합동식3. 중국인의 나머지 정리Math/Number Theory 2023. 8. 3. 22:02
이전 글에서 합동식 $ax \equiv b \bmod n$을 푸는 방법을 알아보았다. 우선, 해가 존재할 조건은 바로 $d = \mathrm{gcd}(a, n)$에 대해 $d \mid b$인 것이다. 또, $x_0$이 위의 합동식의 한 해일 때 $x = x_0 + (n/d)t$ $($단, $t = 0, 1, ..., d-1$$)$가 다른 해임을 알아보았다. 이번 글에서는 여러개의 연립 합동식을 푸는 방법을 알아볼 것이다. 연립 합동식 이제, 다음과 같은 서로 다른 $r$개의 합동식을 생각해보자. $$a_1x \equiv b_1 \bmod m_1$$ $$a_2x \equiv b_2 \bmod m_2$$ $$ ... $$ $$a_rx \equiv b_r \bmod m_r $$ 이 연립 합동식을 풀어볼 것이다..
-
[계산논리] 명제논리의 증명 2. Hilbert System을 이용한 증명Math/Logic 2023. 7. 25. 21:50
증명의 의미 이전 글에서 공부한 내용을 다시 살펴보자. 정해진 공리들을 이용해 주어진 명제식을 참으로 만드는 과정을 증명이라고 하였다. 그리고, 공리들을 이용해 명제식을 참으로 치환할 수 있으면, 해당 명제는 증명 가능하다고 한다. 이를 다음과 같이 표현한다. $$ \vdash_{a} P$$ Hilbert system을 살펴보기 전, 이 표기를 약간 확장해보자. 증명의 확장 어떤 명제식 $P$와 $Q$에 대하여, $P \vdash Q$를 다음과 같이 정의하자 : 정의된 공리와 더불어 $P = T$임을 이용하여 명제식 $Q$가 참임을 증명할 수 있다 여기에서 약간 더 확장해서, 명제식들의 집합 $\Gamma = \left\{P_1, ... , P_n \right\}$에 대해 $\Gamma \vdash Q$..
-
[계산논리] 명제논리의 증명 1. 공리를 이용한 증명Math/Logic 2023. 7. 11. 22:00
지금까지 우리는 어떤 명제식의 참/거짓을 판단하기 위해 진리표를 이용했다. 즉, 명제변수가 갖는 진리값에 따라 명제식이 어떤 값을 갖는지를 확인했던 것이다. 그리고, 명제변수가 어떤 값을 갖든 상관없이 참이 되는 명제식을 항진명제라고 했다. 이번 글에서는, 어떠한 명제식이 참임을 보이는 다른 방법을 알아볼 것이다. 명제논리의 공리 공리$($axiom$)$란, 증명할 필요 없이 자명하게 참이 되는 명제를 말한다. 명제논리에서 사용되는 몇가지 공리를 소개하겠다. Axiom 1. Commutativity Axiom 7. Contradiction $p \wedge q = q \wedge p$ $p \vee q = q \vee p$ $p \wedge \neg p = F$ Axiom 2. Associativity ..
-
[정수론] 합동식2. 선형 합동식Math/Number Theory 2023. 7. 6. 21:43
디오판토스 방정식 디오판토스 방정식은, 정수만을 해로 가질 수 있는 다항 부정방정식이다. 대표적으로 $x^2 + y^2 = z^2$과 같은 방정식이 있으며, 이는 당연히 $x=3,y=4,z=5$와 같은 해를 갖는다. 그 중에서 $ax+by=c$와 같은 형태의 디오판토스 방정식은 해의 존재성과 관련하여 한가지 정리가 있다. Theorem. 선형 디오판토스 방정식 $ax+by=c$는 $d=\mathrm{gcd}(a,b)$에 대해 $d \vert c$일 때만 해를 갖는다. Proof. 필요충분조건이므로, 두 경우에 대해 모두 증명해보겠다. $d=\mathrm{gcd}(a,b)$라면, 어떤 정수 $r, s$에 대해 $a=dr, b=ds$로 나타낼 수 있다. 이때, $ax+by=c$의 해가 존재한다면, 어떤 정수..
-
[계산논리] 명제논리의 문법 4. SatisfyMath/Logic 2023. 7. 5. 18:06
명제식의 모델 이전 글에서, 우리는 모델과 valuation에 대해 알아보았다. 간단하게 정리하자면, valuation은 명제 변수에 특정한 논리값을 대입하는 것을 말한다. 그리고 모델은 명제식을 참으로 만드는 valuation을 말한다. 이제, 어떤 명제식의 모델을 기호로 나타내는 방법을 알아보자. 명제식 $P \in WFF$와 어떤 valuation $v$에 대해 $v(P) = 1$이면, $v$는 $P$의 모델이며, 다음과 같이 나타낸다. $$v \vDash P$$ 여러의 valuation이 명제식 $P$의 모델인 경우, 집합을 이용하여 $\left\{v_1, ..., v_n\right\} \vDash P$와 같이 나타낼 수 있다. 즉, valuation의 집합 $\Gamma$에 대해 $\Gamma ..
-
[정수론] 합동식1. 합동식의 정의Math/Number Theory 2023. 7. 4. 21:41
합동식의 정의 Definition. 양의 정수 $n$과 두 정수 $a, b$에 대하여 만약 $n \vert (a-b)$라면, 법 $n$에 대하여 $a$와 $b$는 합동이라고 하며, 기호로는 $a \equiv b \bmod n$ 으로 나타낸다. 즉, 정수 $n$이 $a-b$를 나눈다면, 즉 $a-b$가 $n$으로 나누어 떨어진다면 $n$에 대하여 $a$와 $b$는 합동인 것이다. 반대로 $a-b$가 $n$으로 나누어 떨어지지 않는다면 $a$와 $b$는 합동이 아니다. 다르게 표현한다면, $\exists k \in \mathbb{Z}\, \mathrm{s.t.} \, a - b = nk$ 라면 $a \equiv b \bmod n$ 이다. 몇가지 예시를 생각해보자. $3 - 24 = -21$인데, $7 \ve..
-
[계산논리] 명제논리의 문법 3. 명제식의 의미와 모델Math/Logic 2023. 7. 1. 18:24
명제식의 의미 이전 글에서 명제식을 정의했다. https://hellworld.tistory.com/20 명제식은 참/거짓, 참과 거짓이 될 수 있는 명제변수, 연결사로 명제변수를 묶은것으로 정의된다. 그리고 진리표를 그려서 명제식의 값을 판단해보았다. 이번 글에서는 명제식을 이해할 수 있는 다른 방법을 소개할 예정이다. 우선, 이전 글에서 소개했던 명제식과 그에 해당하는 진리표를 그려보자. $A$ $B$ $((A \rightarrow B) \wedge \neg A)$ 0 0 1 0 1 1 1 0 0 1 1 0 이 진리표의 의미를 좀 더 자세히 분석해보도록 하겠다. 왼쪽 두 줄은 명제변수 $A$와 $B$가 가질 수 있는 값의 모든 경우의 수를 나타낸 것이다. 명제변수는 참/거짓 $($또는 true/fal..
-
[Web Hacking] Portswigger - CSRF where token validation depends on request methodCoding/Hacking & Security 2023. 3. 7. 09:50
기초적인? CSRF 공격을 해보자. 문제 분석 로그인 후 /my-account 페이지에서 email을 변경할 수 있다. 이 부분에 CSRF 공격을 시도할 수 있을것 같다. Victim에게 CSRF 공격이 포함된 페이지를 전달했을 때 자동으로 그의 email이 변경되도록 해보자. 단, victim이 해당 사이트에 로그인해놓은 상태라는 것을 가정해야 하긴 한다. 목표 Victim이 해당 사이트에 로그인해놓은 상태로 접속하면 자동으로 email이 변경되도록 CSRF를 구성해보자. 그런데 생각해야 할 점이 하나 있다. 사이트의 소스코드를 보면, 변경된 email 값과 함께 CSRF token이 같이 전달되는 모습을 볼 수 있다. 서버에서는 email 변경 요청이 오면 CSRF token을 확인하여 해당 사용자의..