티스토리

neutrinox4b1
검색하기

블로그 홈

neutrinox4b1

thfist-1071.tistory.com/m

그믐​ 님의 블로그입니다.

구독자
15
방명록 방문하기
공지 Wargame, CTF별 검색 키워드⋯ 모두보기

주요 글 목록

  • [CryptoHack] RSA Starter 5 풀이 공캐 키로 주어진 인자들을 가지고 암호화하였다. N = 882564595536224140639625987659416029426239230804614613279163 e = 65537 c = 77578995801157823671636298847186723593814843845525223303932 이 상황에서 c를 해독한다. 이전 문제에서 RSA의 원리를 공부하였고 여기서 비밀 키 d를 찾으면 된다. 그러기 위해 phi(N)을 구해야하고 이를 쉽게 하려면 N을 인수분해해야한다. N은 생각보다 매우 작은 수이다. 이 정도로 작은 수는 쉽게 안수분해된다. http://factordb.com/index.php?query=882564595536224140639625987659416029426239230804.. 공감수 1 댓글수 0 2023. 6. 29.
  • [CryptoHack] RSA Starter 4 설명 개인 키 d는 해당 공개 키로 생성된 암호문을 해독하는데 사용된다. (메시지를 "서명"하는데도 사용되지만 이는 나중에 설명할 것이다.) 개인 키는 암호화 기능을 빠르게 반전시킬 수 있는 "트랩도어"이다. RSA 가 잘 구현되어 있고 개인 키가 없을 때, 암호문을 해독하는 갖아 빠른 방법은 모듈러를 분해하는 것이다. 두 개의 소수가 주어진다. : p = 857504083339712752489993810777 q = 1029224947942998075080348647219 그리고 지수: e = 65537 개인 키 d는 무엇인가? 풀이 RSA에서 $d$는 $\phi(N)$에 대한 $e$의 역원이다. $\therefore d = e^{-1} \bmod \phi(N)$ 이에 대해서는 RSA 원리를 찾아보면 .. 공감수 0 댓글수 0 2023. 6. 2.
  • [CryptoHack] RSA Starter 3 설명 RSA는 모듈러 N의 인수분해의 어려움에 의존한다. 소인수를 찾을 수 있으면, N의 Euler totient를 계산하여 암호문을 해독할 수 있다. 주어진 $N = p * q$ 및 두 개의 소수: p = 857504083339712752489993810777 q = 1029224947942998075080348647219 N의 totient는 무엇인가? 풀이 수론에서, Euler's totient function은 주어진 정수 n까지 서로소인 양의 정수 갯수를 말한다. Euler's totinet function은 곱셈적 함수이다. 두 정수 m, n 이 서로소인 경우에 $\phi (mn) = \phi (m) \phi (n)$이 성립한다. 또한 정의에 따라, 소수 p에 대해 $\phi (p) = p-1.. 공감수 0 댓글수 0 2023. 6. 2.
  • [CryptoHack] RSA Starter 2 설명 RSA암호화는 일반적으로 $N = p * q$라는 두 소수의 곱인 $N$과 지수 $e$를 사용해서 메시지를 모듈러 지수화한 것이다. 지수와 계수는 함께 RSA "공개 키" $(N, e)$를 형성한다. $e$의 가장 일반적인 형태는 0x10001 또는, 65537이다. 지수 $e = 65537$ 과 소수 $p = 17$ 및 $q = 23$을 사용하여 숫자 12를 "암호화"한다. 암호문은 무엇인가? 풀이 e = 0x10001 p = 17 q = 23 N = p*q print(pow(12, e, N))​ 공감수 0 댓글수 0 2023. 6. 2.
  • [CryptoHack] RSA Starter 1 설명 RSA의 모든 작업에는 모듈러 지수가 포함된다. 모듈러 지수는 암호화에서 광범위하게 사용되는 연산이며, 일만적으로 다음과 같이 작성된다. $2^{10} \bmod 17$ 어떤 숫자를 특정 거듭제곱($2^{10} = 1024$)로 올린 다음 나머지를 다른 숫자 ($1024 \bmod 17 \equiv 4$)로 나누는 것으로 생각할 수 있다. 파이썬에는 이 연산을 수행하기 위한 내장 연산자가 있다. pow(base, exponent, modulus) RSA에서 모듈러 지수화는 소인수분해 문제(IFP)와 함께 "트랩도어 기능" 을 구축하는데 도움이 된다. 이것은 한 방향으로 계산하기는 쉽지만, 올바른 정보가 없으면 역방향으로 계산하기 어려운 함수이다. 이를 통해 메시지를 암호화할 수 있으며 키를 가진 사.. 공감수 0 댓글수 0 2023. 6. 2.
  • Sage 설치 맥북에서 Sage를 설치했었는데 터미널에서 명령어가 먹지 않아서 다시 설치하니까 되네요. 설치 주소를 저장해두려고 합니다. sage(System for Algebra and Geometry Experimentation)는 크립토 문제를 풀 때 사람들이 자주 쓰는 도구입니다. python에 기반하고 있어서 어렵지 않게 사용 가능합니다. 그 전에는 문제를 풀 때, python으로 풀었는데 이번 TJCTF에서 몰라서 못 푸는 경우가 발생하여 이 참에 익혀보려고 합니다. https://www.sagemath.org/ SageMath Mathematical Software System - Sage SageMath is a free and open-source mathematical software system. .. 공감수 0 댓글수 0 2023. 5. 30.
  • Fault Attack on RSA CRT https://neutrinox4b1.github.io/blog/2023/Invalid_RSA_decryption_code/ Invalid_RSA_decryption_code | Neutrinox4b1 ⚛ When d is the private key, RSA decryption using CRT is done as follows: mp = c^dp mod p (dp = d mod p-1) mq = c^dq mod q (dq = d mod q-1) qinvp = q^(-1) mod p s = (mp-mq) mod p m = mq+sqinvpq Unfortunately, I implemented the decryption code incorrectly. In neutrinox4b1.github.io 핵테온.. 공감수 0 댓글수 0 2023. 5. 17.
  • [CryptoHack] Bean Counter Background 파이크립토의 카운터 모드가 제가 원하는 대로 작동하는 데 어려움을 겪었기 때문에 ECB 모드를 CTR로 직접 전환했습니다. 제 카운터는 위아래로 움직일 수 있어서 암호 분석가들을 따돌릴 수 있습니다! 그들이 제 사진을 읽을 수 있는 가능성은 전혀 없습니다. 분석 카운터 모드? CTR? 이게 무슨 말일까 from Crypto.Cipher import AES KEY = ? class StepUpCounter(object): def __init__(self, value=os.urandom(16), step_up=False): self.value = value.hex() self.step = 1 self.stup = step_up def increment(self): if self.stup:.. 공감수 0 댓글수 0 2023. 5. 8.
  • [CryptoHack] Symmetry 문제 설명 OFB, CTR 또는 CFB와 같은 일부 블록 사이퍼 모드는 블록 사이퍼를 스트림 사이퍼로 변환합니다. 스트림 암호의 기본 개념은 의사 랜덤 키 스트림을 생성한 다음 일반 텍스트와 XOR하는 것입니다. 스트림 암호의 한 가지 장점은 패딩 없이 임의의 길이의 평문으로 작업할 수 있다는 것입니다. OFB는 모호한 암호 모드로, 요즘에는 CTR을 사용하는 것보다 실질적인 이점이 없습니다. 이번 챌린지는 OFB의 특이한 속성을 소개합니다. from Crypto.Cipher import AES KEY = ? FLAG = ? @chal.route('/symmetry/encrypt///') def encrypt(plaintext, iv): plaintext = bytes.fromhex(plaintext) .. 공감수 0 댓글수 0 2023. 5. 7.
  • [CryptoHack] Flipping Cookie 제 웹사이트를 위한 쿠키를 얻을 수 있지만 flag를 읽는 데 도움이 되지 않습니다... 제 생각에는 말이죠. from Crypto.Cipher import AES import os from Crypto.Util.Padding import pad, unpad from datetime import datetime, timedelta KEY = ? FLAG = ? @chal.route('/flipping_cookie/check_admin///') def check_admin(cookie, iv): cookie = bytes.fromhex(cookie) iv = bytes.fromhex(iv) try: cipher = AES.new(KEY, AES.MODE_CBC, iv) decrypted = cipher.d.. 공감수 0 댓글수 0 2023. 5. 4.
  • Pollard's p-1 algorithm HTML 삽입 미리보기할 수 없는 소스 폴라드의 p-1 알고리즘? 폴라드의 p-1알고리즘은 폴라드가 1974년 폴라드가 발견한 소인수분해 알고리즘이다. 특수한 유형에서 어떤 수 n-1의 소인수들이 매우 많거나 작은 소인수들이 많은 자연수에 적합하다고 한다. 이름이 p-1인 이유로 주어진 정수 n을 소인수분해 하기 위해 n의 소인수 p를 알아내고자, 페르마의 소정리에서 p-1을 활용하기 때문이다. 원리 pollard's p-1 algorithm은 페르마의 소정리를 이용한다. n이 p라는 소인수를 가진다고 하자. p와 서로소인 a에 대해서, 페르마의 소정리 $a^{p-1} \equiv 1 \pmod p$가 성립한다. a를 보통 2로 많이 사용한다. $a^{p-1} \equiv 1 \pmod p$ 이므로 $a.. 공감수 0 댓글수 0 2023. 5. 3.
  • 페르마의 인수분해(Fermat's factorization) HTML 삽입 미리보기할 수 없는 소스 https://en.wikipedia.org/wiki/Fermat%27s_factorization_method Fermat's factorization method - Wikipedia From Wikipedia, the free encyclopedia Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares: N = a 2 − b 2 . {\displaystyle N=a^{2}-b^{2}.} That difference is algebr en.wikipedia.org .. 공감수 3 댓글수 0 2023. 4. 27.
  • [CryptoHack] ECB CBC WTF 문제 설명 여기서는 CBC로 암호화할 수 있지만 ECB로만 해독할 수 있습니다. 서로 다른 모드이기 때문에 약점이 될 수는..없겠죠..? Play at https://aes.cryptohack.org/ecbcbcwtf/ ECB CBC WTF Hex Encoder/Decoder This is a convenient encoder designed for ASCII Hex translations. It won't work for decoding hex to byte streams and will just show [unprintable] in that case. aes.cryptohack.org 문제 풀이 from Crypto.Cipher import AES KEY = ? FLAG = ? @chal.route.. 공감수 1 댓글수 0 2023. 4. 21.
  • [CryptoHack] ECB Oracle 개념 설명 ECB is the most simple mode, with each plaintext block encrypted entirely independently. In this case, your input is prepended to the secret flag and encrypted and that's it. We don't even provide a decrypt function. Perhaps you don't need a padding oracle when you have an "ECB oracle"? ECB는 가장 간단한 모드로, 각 일반 텍스트 블록이 완전히 독립적으로 암호화된다. 이 경우 입력 내용이 비밀 플래그 앞에 추가되고 암호화되며, 그게 전부이다. 암호 해독 기능도 제공하지.. 공감수 0 댓글수 0 2023. 4. 19.
  • [CryptoHack] Passwords as Keys 개념 설명 대칭 키 알고리즘의 키는 비밀번호나 기타 예측 가능한 데이터가 아닌 무작위 바이트여야 한다. 무작위 바이트는 암호학적으로 안전한 의사 난수 생성기(CSPRNG)를 사용하여 생성해야 한다. 어떤 식으로든 키를 예측할 수 있는 경우 암호의 보안 수준이 낮아지고 암호 텍스트에 엑세스한 공격자가 암호를 해독할 수 있다. ! PRNG는 Pseudo RandomNumber Generator이고 CSPRNG는 앞에 Cryptography Secure가 붙는다. 난수 생성에 대해서는 다른 글에서 다뤄보자. 키가 무작위 바이트처럼 보인다고 해서 반드시 그게 무작위라는 것은 아니다. 이 경우에 키는 해싱 함수를 사용하여 비밀번호에서 파생된 것이므로 암호문 해독이 가능하다. 이 챌린지의 경우, 엔드포인트*에 대한.. 공감수 0 댓글수 0 2023. 4. 7.
  • [CryptoHack] Modes of Operation Starter 개념 설명(?) 이전 과제에서는 AES가 데이터 블록에서 키 순열을 수행하는 방법을 보여주었다. 실제로는 단일 블록보다 더 긴 메시지를 암호화해야한다. 작동 모드는 더 긴 메시지에 AES와 같은 암호를 사용하는 방법을 설명한다. 모든 모드에는 잘못 사용할 경우 심각한 약점이 있다. 이 카테고리의 도전 과제는 API와 상호작용하고 이러한 약점을 악용할 수 있는 웹 사이트의 다른 다른 섹션으로 이동한다. 인터페이스에 익숙해져서 다음 플래그에 도전해보자. https://aes.cryptohack.org/block_cipher_starter/ Modes of Operation Starter Description The previous set of challenges showed how AES performs a.. 공감수 0 댓글수 0 2023. 4. 7.
  • [CryptoHack] Bringing It All Together 개념 설명 키 확장 단계 외에도 모든 단계를 스케치했다. SubBytes가 혼동을 제공하고 ShiftRows와 MixColumns가 확산을 제공하는 방법과 이 두 속성이 어떻게 함께 작동하여 상태 행렬에 비선형 변환을 반복적으로 순환시키는지 살펴보았다. 마지막으로 AddRoundKey는 이 substitution-permutation 네트워크에 key를 시드로 하여 암호를 keyed permutation으로 만든다. 복호화에는 "Structure of AES" 챌린지에 설명된 단계를 역으로 수행하여 역연산을 적용하는 것이 포함된다. 여전히 KeyExpansion(키 확장) 을 먼저 실행해야 하며 라운드 키는 역순으로 사용된다는 점에 유의해야 한다. XOR에는 self-inverse(자기 반전) 속성이 있.. 공감수 1 댓글수 0 2023. 3. 31.
  • [CryptoHack] Diffusion through Permutation 개념 설명 순열(Permutation)을 통한 확산. 우리는 S-box 치환이 어떻게 혼란(confusion)을 일으키는지 보았다. Shannon(섀넌)이 설명한 다른 중요한 속성은 "확산(Diffusion)"이다. 이것은 암호 입력의 모든 부분이 어떻게 출력의 모든 부분으로 퍼져야 하는지와 관련이 있다. 치환(Substitution)은 그 자체로 비 선형성을 생성하지만 전체 상태에 걸쳐 비선형성을 분산시키지는 않는다. 확산이 없으면 같은 위치에 있는 같은 바이트는 각 라운드에 동일한 변환이 적용된다. 이를 통해 암호 분석가는 상태 행렬의 각 바이트 위치를 개별적으로 공격할 수 있다. 한 바이트에 적용된 치환이 다른 모든 바이트에 영향을 미치도록 상태 행렬을 스크램블링(scrambling)하여 (가역적인.. 공감수 0 댓글수 0 2023. 3. 30.
  • [CryptoHack] Confusion through Substitution 개념 설명 Confusion through Substitution (치환을 통한 혼란) 각 AES 라운드의 첫 번째 단계는 SubBytes이다. 여기에는 상태 행렬의 각 바이트를 가져와서 미리 설정된 16x16짜리 조회 테이블(lookup table)의 다른 바이트로 대체하는 작업이 포함된다. lookup table은 줄여서 "Substitution box(치환 박스)" 또는 "S-box"라고 하며, 처음 볼 때는 당황 할 수도 있다. 그것을 파헤쳐보자. 1945년 미국 수학자 Claude Shannon(클로드 섀넌)은 정보 이론에 관한 획기적인 논문을 발표했다. 해당 논문에서는 보안 암호의 필수 속성으로 "혼란(confusion)"을 인식하였다. "혼란"은 암호문과 키 사이의 관계가 가능한 복잡해야 함.. 공감수 0 댓글수 0 2023. 3. 22.
  • [CryptoHack] Round Keys 개념 설명 Round Keys(라운드 키) 지금은 KeyExpansion(키 확장)단계에 대한 자세한 내용은 건너뛰겠다. 요점은 16byte 키를 가져와서 초기 키에서 파생된 "라운드 키"라고 하는 11개의 4x4행렬을 생성하는 것이다. 이러한 "라운드 키 round key"를 통해 AES는 우리가 제공한 단일 키에서 추가 마일리지를 얻을 수 있다. (추가적인 이점이 있다는 듯) 다음 단계인 초기 키 추가 단계(initial key addition)에는 단일(하나의) AddRoundKey단계가 있다. AddRoundKey단계는 간단하다. 현재 상태 배열(state)과 라운드 키를 XOR한다. AddRoundKey는 각 라운드의 마지막 부분에서도 발생한다. AddRoundKey는 단순한 순열이라기보다는 ".. 공감수 0 댓글수 0 2023. 3. 21.
  • [CryptoHack] Structure of AES https://cryptohack.org/courses/symmetric/aes2/ CryptoHack – Home A fun, free platform to learn about cryptography through solving challenges and cracking insecure code. Can you reach the top of the leaderboard? cryptohack.org 너무 길어서 링크로 대체한다. 개념 설명 AES의 구조. 키 없이 되돌릴 수 없는 키 순열을 만들어내기 위해, AES는 입력에 많은 수의 애드혹(ad-hoc)혼합 작업을 적용한다. 이는 우아한 개별 수학적 문제를 기반으로 하는 RSA와 같은 공개 키 암호 시스템과 극명한 대조를 이룬다. AES는 훨씬 덜 우.. 공감수 0 댓글수 0 2023. 3. 21.
  • [CryptoHack] Resisting Bruteforce 개념 설명 (Resisting Bruteforce) 무차별 대입 공격 저항. 블록 암호가 안전하다면, 공격자가 AES의 출력을 의사 난수 순열(pseudorandom permutation)과 구별할 방법이 없어야 한다. 게다가 가능한 모든 키를 무차별 대입하는 것보다 순열을 최소화하는 더 좋은 방법이 없어야 한다. 때문에 학계에서는 해당 공격이 실질적으로 불가능하더라도 키를 무차별 대입하는 것보다 수행하는데 더 적은 단계가 필요한 공격을 발견할 수 있는 경우 암호가 이론적으로 "파손"(broken)되었다고 간주한다. ! 128비트 키 스페이스를 무차별 대입하는 것이 얼마나 어려울까? (https://crypto.stackexchange.com/questions/48667/how-long-would-it.. 공감수 0 댓글수 0 2023. 3. 21.
  • [CryptoHack] Keyed Permutations 대칭 암호학? 시작입니다. 사실 그 전에 계속 중국인의 나머지 정리를 이해하기 쉽게 증명해서 글을 쓰고자 했는데 너무 어려워서 다음에 쓰려고 미루고.. 진도나 나갑시다. 이번 대회에서는 그냥 sympy에서 crt를 사용하는 걸로.. Keyed Permutation (키드 순열) AES는 다른 우수한 블록 암호와 마찬가지로 "Keyed Permutation"을 수행한다. 즉 수행할 순열을 결정하는 키를 사용하여 가능한 모든 입력 블록을 특정한 출력 블록에 매핑하는 것이다. ! '블록'은 모든 종류의 데이터를 나타낼 수 있는 고정된 수의 비트 혹은 바이트를 나타낸다. AES는 블록을 처리하고 다른 블록을 출력한다. 특히 AES-128로 알려진 128비트(16byte) 블록과 128비트 키에서 작동하는 AES.. 공감수 0 댓글수 0 2023. 3. 20.
  • [CryptoHack] Modular Binomials 문제 설명 다음 방정식을 재배열하여 소수 p, q를 구하여라. N = p*q c1 = (2*p + 3*q)**e1 mod N c2 = (5*p + 7*q)**e2 mod N 문제 풀이 이번 문제를 풀기 위해서 정말 많은 개념들을 찾아봤다. 나는 합동식에 익숙치가 않아서 너무 어려웠던 문제이다.. $N = pq$이고, $c_1 = (2p + 3q)^{e_1} \bmod N$, $c_2 = (5p + 7q)^{e_2} \bmod N$이다. 우리는 p나 q를 중 하나를 구하면 N을 나눠서 다른 하나를 구할 수 있다. 연립 방정식을 푸는 것처럼 풀이가 가능하다. 위에 식은 이항으로 n제곱 되어있는데 이게 어떻게 연립방정식처럼 풀 수 있는가? Freshman's dream(대학교 1학년의 꿈)이 성립한다. $(x.. 공감수 0 댓글수 1 2023. 3. 10.
  • [CryptoHack] Adrien's Signs 문제 설명 애드리언은 symbol(아마 르장드르 기호)와 마이너스 기호를 통해 메시지를 암호화 하는 방법을 찾고 있어요. flag를 복구할 방법을 알고 있나요? 문제 풀이 문제는 그냥 이전 개념들을 사용해서 푸는 것으로 보인다. from random import randint a = 288260533169915 p = 1007621497415251 FLAG = b'crypto{????????????????????}' def encrypt_flag(flag): ciphertext = [] plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag]) for b in plaintext: e = randint(1, p) n = pow(a, e, p) if b == '1'.. 공감수 0 댓글수 0 2023. 3. 9.
  • [CryptoHack] Chinese Remainder Theorem 개념 설명 중국인의 나머지 정리 (CRT) 중국인의 나머지 정리는 모듈리(mod p에서 p)가 서로소(coprime)일 경우 선형 합동 집합에 대한 특수한 해를 제공한다. 즉, 임의의 정수 집합 $a_i$와 pairwise(쌍) 서로소(paiwise coprime integers) $n_i$가 주어졌을 때 다음과 같은 선형 합동식이 성립한다. ! 참고로, "pairwise coprime integers"는 우리가 정수 집합 ${n_1, n_2, ..., n_i}$를 가지고 있을 때, 집합에서 선택된 모든 정수 쌍은: $\gcd(n_i, n_j) = 1$임을 의미한다. $ x \equiv a_1 \mod n_1$ $ x \equiv a_2 \mod n_2$ . . . $x \equiv a_n \mod n_.. 공감수 1 댓글수 0 2023. 3. 7.
  • [CryptoHack] Modular Square Root 개념 설명 모듈러 제곱근 르장드르 기호(Legendre Symbol)에서 우리는 숫자가 소수(prime) 모듈러의 제곱근인지를 결정할 수 있는 빠른 방법을 소개했다. 우리는 더 나아갈 수 있다: 그러한 제곱근을 효율적으로 계산하기 위한 알고리즘이 있다. Tonelli-Shanks라고 불리는 것이 있는데, 이것은 19세기에 이탈리아 인에ㅕ의해 처음 묘사되었고 1970년대에 Daniel Shanke에 의해 독립적으로 재발견 되었다는 사실에서 재미있는 이름을 얻었다. 2가 아닌 모든 소수는 모든 홀수가 다음과 같은 합동성을 띄기 때문에 $p \equiv 1 \mod 4$ 또는 $p \equiv 3 \mod 4$ 형식이다. 앞선 문제의 힌트처럼 $p \equiv 3 \mod 4$의 경우, 제곱근을 계산하기 위한.. 공감수 0 댓글수 0 2023. 3. 6.
  • [CryptoHack] Legendre Symbol 개념 설명 르장드르 기호 2차 잉여에서 우리는 제곱근 정수 모듈러를 취하는 것이 무슨 의미인지 배웠다... 우리는 또한 제곱근을 가지는 것이 항상 가능한 것은 아니라는 것을 알았다. 이전의 경우 $p = 29$일때 간단한 루트 계산으로도? 충분히 빨랐지만 p가 커질수록 이 방법은 엄청나게 불합리해진다. 다행히도 르장드르 덕분에 정수가 한 번의 계산으로 2차 잉여인지 확인할 수 있는 방법이 있다. 다음에서 우리는 소수 p에 대한 모듈러 작업을 한다고 가정할 것이다. 르장드르 기호를 살펴보기 전에 2차 잉여의 흥미로운 성질을 보기 위해 잠시 돌아가보자. 이차 잉여 * 이차 잉여 = 이차 잉여 이차 잉여 * 이차 비잉여 = 이차 비잉여 이차 비잉여 * 이차 비잉여 = 이차 잉여 ! 이것을 쉽게 기억하는 방법은.. 공감수 0 댓글수 0 2023. 3. 6.
  • [CryptoHack] Quadratic Residues 개념 설명 제곱 잉여 우리는 모듈러 연산에서 곱셈과 나눗셈에 대해서 살펴보았다. 그러나 제곱근 모듈러를 정수로 취하는 것은 뭘 의미할까? 해당 논의를 위해 모듈러 $p = 29$를 사용해보자. 우리는 정수 $a = 11$을 취하여 $a^2 = 5 \mod 29$ 임을 계산할 수 있다. $a = 11, a^2 = 5$로서 우리는 5의 제곱근이 11이라고 말한다.(?) 기분은 좋지만, 이제 18의 제곱근에 대해서 생각해보자. 위에서, 우리는 $a^2 = 18$인 정수 a를 찾을 필요가 있다는 것을 안다. 첫번째 아이디어는 $a=1$부터 시작하여 $a=p-1$까지 루프를 도는 것이다. 이 논의에서 p가 너무 크지 않으면 우리는 빨리 찾아낼 수 있을 것이다. 시도해보자. 이것을 코딩해보고 무엇을 찾는지 보자. .. 공감수 0 댓글수 1 2023. 3. 5.
  • [CryptoHack] Modular Arithmetic 2 개념 설명 모듈러 연산 2 우리는 지난 문제로부터 모듈러 p를 고를 것입니다. 그리고 p가 소수일때의 경우로 제한합니다. 정수 모듈러 p는 체(field) $F_p$를 정의합니다. ! 만약 모듈러가 소수가 아니라면, 정수 모듈러 n 집합은 환(ring)을 형성합니다. 유한체 $F_p$는 정수 $\{0,1..., p-1\}$의 집합이며, 덧셈과 곱셈 모두에서 $a+b=0$, $a\times b = 1$과 같이 집합의 모든 원소 a에 대한 역원이 존재합니다. ! 덧셈과 곱셈의 항등원(identity element)는 서로 다릅니다! 항등원은 연산자와 함께 동작할 때 아무것도 수행하지 않아야 합니다. : $a+0 = a$ : $a \times 1 = a$ $p = 17$을 선택한다고 가정합시다. $3^{17}.. 공감수 0 댓글수 0 2023. 1. 4.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.