picoCTF2022

basic-mod2

def Pico(s):
    return ("picoCTF{"+s+"}")

def extgcd(a,b):
    x0,y0,x1,y1=1,0,0,1
    while(b!=0):
        q,a,b=a//b,b,a%b
        x0,x1=x1,x0-q*x1
        y0,y1=y1,y0-q*y1
    return a,x0,y0

def modinv(a,m):
    g,x,y=extgcd(a,m)
    if g!=1:
        raise Exception('modular inverse does not exist')
    else:
        return x%m


s=""
v=list(map(int, input().split()))
for i in range(len(v)):
    v[i]%=41
    v[i]=modinv(v[i],41)
    if 1<=v[i]<=26:
        s+=chr(64+v[i])
    elif 27<=v[i]<=36:
        s+=str(v[i]-27)
    elif v[i]==37:
        s+="_"

print(Pico(s))

Rail fence cipher
レールフェンス暗号とは文字列をジグザクに配置して上から順に横に読んでいく古典暗号である。
例

暗号化の実装

s=input()
N=int(input())
v = np.zeros((N, len(s)))
v = [[0 for j in range(len(s))] for i in range(N)]
for i in range(N):
    for j in range(len(s)):
        v[i][j]="."
h=1
up=True
for i in range(len(s)):
    v[h-1][i]=s[i]
    if h==N :
        up=False
    if h==1 :
        up=True
    if up:
        h+=1
    else:
        h-=1
for i in range(N):
    for j in range(len(s)):
        print(v[i][j]+" ",end="")
    print("")
ans=""
for i in range(N):
    for j in range(len(s)):
        if v[i][j]!=".":
            ans+=v[i][j]
print(ans)

入力
レールの本数を3、平文をWE ARE DISCOVERED RUN AT ONCEとする
入力

WEAREDISCOVEREDRUNATONCE
3

出力

W . . . E . . . C . . . R . . . U . . . O . . . 
. E . R . D . S . O . E . E . R . N . T . N . E
. . A . . . I . . . V . . . D . . . A . . . C .
WECRUOERDSOEERNTNEAIVDAC

復号
レールの本数がわかってる場合、周期性を利用して愚直にやっていくだけである
レールの本数がわかっていない場合ブルートフォースアタックによって平文を求められる
xを対角線の本数、yを最後の対角線の不足数、Lを暗号文の長さとすると
N+(x-1)(N-1)=L+yが成り立つ
ここでNを適当に一つ定めると、l=L-Nとして
(x-1)(N-1)=l+yと書ける。ここでx-1は(x-1)*(N-1)がl以上となる最小の整数なのでx-1は一意に定まり、自動的にyも一意に定まる
また、N<LなのでO(L)で求められる

実装

s=input()
L=len(s)
for i in range(2,len(s)):
    ans = ["."] * len(s)
    p=0
    x=(i-1)*2
    down=True
    for j in range(i):
        k=j
        a=True
        while k<len(s) and p<len(s):
            ans[k]=s[p]
            p+=1
            if x!=(i-1)*2:
                if a:
                    k+=x
                    a=False
                else:
                    k+=(i-1)*2-x
                    a=True
            else:
                k+=x
        if down:
            x-=2
            if x==0:
                x=(i-1)*2
    for i in range(len(s)):
        print(ans[i],end="")
    print(" ")

入力

WECRUOERDSOEERNTNEAIVDAC

出力

WEERCNRTUNOEEARIDVSDOAEC 
WEAREDISCOVEREDRUNATONCE
WUEVROEENDTRCDNAESROACIE
WRSTDNOUEOEEAAEECRRICVND
WRDRAAINSUEOOTVCDNEECREE
WCEONAAITERREUDENVCDERSO
WCODENAAITESEREURORNVCDE
WCODENEVCDATESEREURORNIA
WCODENEIDCAVATESEREURORN
WCODERTEIDCAVANNESEREURO
WCORSERTEIDCAVANNEODEREU
WERORSERTEIDCAVANNEODEUC
WECRORSERTEIDCAVANNEODEU
WECRUORSERTEIDCAVANNEODE
WECRUOERSERTEIDCAVANNEOD
WECRUOERDSERTEIDCAVANNEO
WECRUOERDSOERTEIDCAVANNE
WECRUOERDSOEERTEIDCAVANN 
WECRUOERDSOEERNTEIDCAVAN
WECRUOERDSOEERNTNEIDCAVA
WECRUOERDSOEERNTNEAIDCAV
WECRUOERDSOEERNTNEAIVDCA

3行目にちゃんと文章が出てきましたね。成功です

解答
picoCTF{WH3R3_D035_7H3_F3NC3_8361N_4ND_3ND_EB4C7D74}

substitution0
換字式暗号です。頻度分析をかけましょう
原文

UHQKRNWLFIYJBTODCZVAXEGSMP

Lrzrxdot Jrwzutk uzovr, gfal u wzuer utk vauarjm ufz, utk hzoxwla br alr hrrajr
nzob u wjuvv quvr ft glfql fa guv rtqjovrk. Fa guv u hruxafnxj vquzuhurxv, utk, ua
alua afbr, xtytogt ao tuaxzujfvav—on qoxzvr u wzrua dzfpr ft u vqfrtafnfq dofta
on efrg. Alrzr grzr ago zoxtk hjuqy vdoav truz otr rsazrbfam on alr huqy, utk u
jotw otr truz alr oalrz. Alr vqujrv grzr rsqrrkftwjm luzk utk wjovvm, gfal ujj alr
uddruzutqr on hxztfvlrk wojk. Alr grfwla on alr ftvrqa guv erzm zrbuzyuhjr, utk,
auyftw ujj alftwv ftao qotvfkrzuafot, F qoxjk luzkjm hjubr Ixdfarz noz lfv odftfot
zrvdrqaftw fa.

Alr njuw fv: dfqoQAN{5XH5717X710T_3E0JX710T_7H755H1U}

これを使いました
https://tools.m-bsys.com/original_tooles/frequency_analysis.php
追記
自分でも実装した。Pythonむずかしいです(本当は返り値不要)

def th(s):
    d = {}
    for i in range (len(s)-2):
        a=""
        a+=s[i]
        a+=s[i+1]
        a+=s[i+2]
        if a in d:
            d[a]+=1
        else :
            d[a]=1
    sorted(d.items())
    for k,v in d.items():
        print(k,v)
    return d
s=input()
def tw(s):
    d = {}
    for i in range (len(s)-1):
        a=""
        a+=s[i]
        a+=s[i+1]
        if a in d:
            d[a]+=1
        else :
            d[a]=1
    sorted(d.items())
    for k,v in d.items():
        print(k,v)
    return d
s=input()
def on(s):
    d = {}
    for i in range (len(s)):
        a=""
        a+=s[i]
        if a in d:
            d[a]+=1
        else :
            d[a]=1
    sorted(d.items())
    for k,v in d.items():
        print(k,v)
    return d
    
s=input()
co_th=th(s)
co_tw=tw(s)
co_on=on(s)

1文字だとrが最多で59文字。3文字だとutkが7、alrが6、Alrが4なのでrがe,alrはtheだと予想できます。さらに最後のdfqoQAN{5XH5717X710T_3E0JX710T_7H755H1U}がpicoCTFにしか見えないのでそうします。
これらを踏まえると最初の分は
UHQKRNWLFIYJBTODCZVAXEGSMP
##C#EF#HI######P###T######
となるのでC#EFの部分からアルファベットの昇順だとわかります。よってフラグは
picoCTF{5UB5717U710N_3V0LU710N_7B755B1A}

ちなみにhttps://www.guballa.de/substitution-solver
これ使うと一発で答え出るらしい。なああああああ

transposition-trial
3文字ごとに文字がシャッフルされたらしいです
暗号

heTfl g as iicpCTo{7F4NRP051N5_16_35P3X51N3_VC85A020}E

初手からどうみてもheT->Theですよね。考察終わり
実装

s=input()
s+="   "
ans=""
for i in range(len(s)//3):
    ans+=s[i*3+2]
    ans+=s[i*3]
    ans+=s[i*3+1]
print(ans)

The flag is picoCTF{7R4N5P051N6_15_3XP3N51V3_5C82A0E0}

Vigenere
超がつくほどの有名暗号ヴィジュネル暗号です。
Pを平文、Sを暗号文、Kを鍵とすると以下の等式が成り立ちます
S[i]=P[i]+Ki
つまりP[i]=S[i]-Ki
また、|P|=|S|>|K|のときはKを必要な長さだけ繰り返し使います

実装

s=input()
key=input()
j=0
ans=""
for i in range(len(s)):
    a=ord(s[i])
    if not(65<=a<=90) and not(97<=a<=122):
        ans+=s[i]
    else :
        b=ord(key[j])
        j+=1
        if j==len(key):
            j=0
        if 65<=a<=90:
            a-=b
            if a<0:
                a+=26
            elif a>=26:
                a-=26
            a+=65
            ans+=chr(a)
        else :
            b+=32
            a-=b
            if a<0:
                a+=26
            elif a>=26:
                a-=26
            a+=97
            ans+=chr(a)
print(ans)

入力

rgnoDVD{O0NU_WQ3_G1G3O3T3_A1AH3S_a23a13a5}
CYLAB

出力

picoCTF{D0NT_US3_V1G3N3R3_C1PH3R_y23c13p5}

ここからは200点問題
diffie-hellman
みんな大好きディフィー・ヘルマン鍵共有問題とは
素数p,p-1を割り切る素数qと{1,2...,p-1}の要素であってmod pで見た時に初めてg^1,g^2...,g^(q-1)が1ではなく、かつg^qがはじめて1となるようなgをとり、0<=a,b<qを満たす整数a,bを用意します。AAさんがaをBBさんがbを持ちます。このときg,p,qは公開で、a,bは秘密です
AAさんA=g^a(mod p)
BBさんB=g^b(mod p)
AAさんとBBさんでAとBを送りあう
AAさんKA=B^a(mod p)
BBさんKB=A^b(mod p)
とすると自明であるがKA=KBとなるのでこれを秘密鍵として使用する暗号である
この問題では秘密鍵でシーザー暗号をやるというものでした。普通のシーザーはアルファベットに対してのみ使いますがこの問題では数字も回りだすので少し大変でしたが軽く考察するとmod36で考えたら十分だとわかります。シーザー暗号なので両方向に回転することを忘れちゃダメ
実装

p=int(input())
g=int(input())
anu=int(input())
bnu=int(input())
A=pow(g,anu,p)
B=pow(g,bnu,p)
KA=pow(B,anu,p)
KB=pow(A,bnu,p)
#KA==KBとなる
s=input()
KA%=36
ans=""
ans2=""
for i in range(len(s)):
    a=ord(s[i])
    if s[i]=="_":
        ans+="_"
    else:
        if 48<=a<=57:
            a+=KA
            if a>57:
                a+=7
        else:
            a+=KA
            if a>90:
                a-=43
        ans+=chr(a)
print(ans)
KB=36-KA
for i in range(len(s)):
    a=ord(s[i])
    if s[i]=="_":
        ans2+="_"
    else:
        if 48<=a<=57:
            a+=KB
            if a>57:
                a+=7
            if a>90:
                a-=43
        else:
            a+=KB
            if a>90:
                a-=43
            if a>57:
                a+=7
        ans2+=chr(a)
print(ans2)

入力

13
5
7
3
H98A9W_H6UM8W_6A_9_D6C_5ZCI9C8I_7IGK58KC

出力

MEDFE1_MBZRD1_BF_E_IBH_A4HNEHDN_CNLPADPH
C4354R_C1PH3R_15_4_817_0U7D473D_2DBF03F7

picoCTF{C4354R_C1PH3R_15_4_817_0U7D473D_2DBF03F7}

以後400点問題です
Sum-O-Primes
ようやくRSA暗号が出てきましたね
与えられたデータは以下の2つです

x = 198e800b4f9e29e69889bc7a42b92dbd764cb22dbeb5fb81b1d9778bfe8c4b85d08a7f990019d537b6856aa1ff7355d0bef66c0a5c954bb4b7e58ac094c42ac1c23d23f8f763e41bbebdfa985505ab3571f8355290d2ca66ac333c4e30f1b7354c37d67db2c13c7e07ca3b6d98283f5042a55e23796ca227f428e0d3a83057510
n = a0ab034d978fdd92e73f3f7536f4f2ff5f4dee70b5f1d319903ec65f2a8ffe729688452d2c1f25a7c330e6bb532580094196f888a20ba7556f0907d8a4884bddbde4c4361582fcf163799a0f49b9d196b32012e1b5a4dabd2a6c9e9a47173f903ae1ebe2db66ebf55471982d52e6cbeb8060dd0f01d950a30ac5a830ad2414c86f97703717752bd20abb528f7738e010a7c3e8116b2c3a6706d900d83ff4afc7ca8b47f6c19d1de00c7ea8666c617a5e33d600b381b263662ad17a5d4262a819a57b357fee702538355ee7723f9c694a3c98999bc2432658c7798119d7a54d5e4c01447c7afcdf36110be0be195cea0828b17f5e86b4702341e7a37babb3db07
c = 497f4e814e3d7093d49c33c9b743748455b82496af6a8900e6d3c899b58a5e8d32fde34dccf882a87859d8508a18fe23088c8b58dd33decb3e9f4c1737c85f0b66114e62efe0da72fcee95619e4d76e7c485f161464f7067237bbcc213bd02b5e2816208333146652395e07f4245dfd654755417d35cc0a27933dd48ab219f31ed73820087c1ec7e2150caf4f5f0de052d14a2e492715e3a3ca24de41240d49494532b4d5fa54c59db08c6d94938f33a489c24a9b4a7d6b2d57164ce7aacdd0707302fded17671d197485c764064ed97d2560274b5ed4994446e8f790e16e05e8dd4b2d39e228a715f70bd012eb7eaec65e67734fad95f55be307e26b2106226

#!/usr/bin/python

from binascii import hexlify
from gmpy2 import mpz_urandomb, next_prime, random_state
import math
import os
import sys

if sys.version_info < (3, 9):
    import gmpy2
    math.gcd = gmpy2.gcd
    math.lcm = gmpy2.lcm

FLAG = open('flag.txt').read().strip()
FLAG = int(hexlify(FLAG.encode()), 16)
SEED = int(hexlify(os.urandom(32)).decode(), 16)
STATE = random_state(SEED)


def get_prime(bits):
    return next_prime(mpz_urandomb(STATE, bits) | (1 << (bits - 1)))


p = get_prime(1024)
q = get_prime(1024)

x = p + q
n = p * q

e = 65537

m = math.lcm(p - 1, q - 1)
d = pow(e, -1, m)

c = pow(FLAG, e, n)


print(f'x = {x:x}')
print(f'n = {n:x}')
print(f'c = {c:x}')

まずp+qとpqがわかってるので解と係数の関係使えばいいんですが如何せん桁がでかすぎるのでsqrtがとれませんでした。なのでsqrtは二分探索で求めました
するとp,qがわかる、つまり秘密鍵dがわかるので基本に倣ってやっていくだけですね。復号したら数字の列が得られたのでbyteに直せばOKです
実装

# 二次方程式x=(-b+-sqrt(b^2-4ac))/2a
def SQRT(x):
    right = 10**700
    left = 1
    while right-left > 1:
        mid = (right+left)//2
        if x == mid*mid:
            return mid
        elif x < mid*mid:
            right = mid
        else:
            left = mid


def sec(a, b, c):
    return (-b+SQRT(b*b-4*a*c))//(2*a), (-b-SQRT(b*b-4*a*c))//(2*a)


def GCD(x, y):
    if x % y == 0:
        return y
    else:
        return GCD(y, x % y)


def LCM(x, y):
    return x//GCD(x, y)*y


def int_to_bytes(x: int) -> bytes:
    return x.to_bytes((x.bit_length()+7)//8, 'big')


n = int('a0ab034d978fdd92e73f3f7536f4f2ff5f4dee70b5f1d319903ec65f2a8ffe729688452d2c1f25a7c330e6bb532580094196f888a20ba7556f0907d8a4884bddbde4c4361582fcf163799a0f49b9d196b32012e1b5a4dabd2a6c9e9a47173f903ae1ebe2db66ebf55471982d52e6cbeb8060dd0f01d950a30ac5a830ad2414c86f97703717752bd20abb528f7738e010a7c3e8116b2c3a6706d900d83ff4afc7ca8b47f6c19d1de00c7ea8666c617a5e33d600b381b263662ad17a5d4262a819a57b357fee702538355ee7723f9c694a3c98999bc2432658c7798119d7a54d5e4c01447c7afcdf36110be0be195cea0828b17f5e86b4702341e7a37babb3db07', 16)
c = int('497f4e814e3d7093d49c33c9b743748455b82496af6a8900e6d3c899b58a5e8d32fde34dccf882a87859d8508a18fe23088c8b58dd33decb3e9f4c1737c85f0b66114e62efe0da72fcee95619e4d76e7c485f161464f7067237bbcc213bd02b5e2816208333146652395e07f4245dfd654755417d35cc0a27933dd48ab219f31ed73820087c1ec7e2150caf4f5f0de052d14a2e492715e3a3ca24de41240d49494532b4d5fa54c59db08c6d94938f33a489c24a9b4a7d6b2d57164ce7aacdd0707302fded17671d197485c764064ed97d2560274b5ed4994446e8f790e16e05e8dd4b2d39e228a715f70bd012eb7eaec65e67734fad95f55be307e26b2106226', 16)
x = int('198e800b4f9e29e69889bc7a42b92dbd764cb22dbeb5fb81b1d9778bfe8c4b85d08a7f990019d537b6856aa1ff7355d0bef66c0a5c954bb4b7e58ac094c42ac1c23d23f8f763e41bbebdfa985505ab3571f8355290d2ca66ac333c4e30f1b7354c37d67db2c13c7e07ca3b6d98283f5042a55e23796ca227f428e0d3a83057510', 16)
x1, x2 = sec(1, -x, n)
e = 65537
m = LCM(x1 - 1, x2 - 1)
d = pow(e, -1, m)
print(pow(c, d, n))
f = pow(c, d, n)
flag = int_to_bytes(f).decode().strip()
print(flag)

出力

38251710328773353864633064751392504756093
picoCTF{ee326097}