はじめに

picoCTFに取り組んで行くときの考えていたことを書き記す。writeupというより、解いた道筋を書いていますので、最短距離を知りたい人にとっては意味わからないものかもしれません。ご了承ください。begginerのお戯れと思って暖かく見守っていただければ幸いです。自身の持っているPCのスペックではdocker環境でCTFを行えないので、colab上でできそうなcryptographyをやってみようと思いました。

開閉

はじめに
Mind your Ps and Qs
The Numbers
caesar
13
interencdec
Custom encryption
ここより下未解決
- C3

[2024/01/21]

Mind your Ps and Qs

In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values 与えられたファイルには以下のことが書かれていた。

Decrypt my super sick RSA:
c: 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n: 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e: 65537

RSAなのでnを素因数分解したいが、自作のプログラムでは時間がかかりすぎる。
今までに大きな数の素因数分解を行うサイトがあることを知っているので、そこで行う。 (factordb) というわけで入力したらすぐに出てきた。

ここからdの求め方やcが大きいので乗算していくのが難しいとか思ってwriteUp見てしまった。
(picoCTF2021 [Cryptography] writeup)
つまり、dを求めるのはモジュロ逆数を求めること、messageはpow関数で行えるそうだ。(powに時間がかかると思ったがそんなことはありませんでした。)モジュロ逆数を求める方法は上記writeUpとは違い、pow関数で行えるようだったのでそこで行った。　　

c= 964354128913912393938480857590969826308054462950561875638492039363373779803642185
n= 1584586296183412107468474423529992275940096154074798537916936609523894209759157543
e= 65537
p = 2434792384523484381583634042478415057961
q = 650809615742055581459820253356987396346063

pq = (p-1)*(q-1)
d = pow(e,-1,pq)
m = pow(c,d,n)

ここでmは数値列として出力されたがどのように文字に変換すればよいのかについて考えていた。
(CryptoHack "INTRODUCTION TO CRYPTOHACK")さんのBytes and Big Integersのところに書いてあることを参考にしたが、やはり文字コードを用いて変換するようであるが、実際どれを用いるのかはわからず。PyCryptodomeをpipして、from Crypto.Util.number import long_to_bytesをインポートして使いました。flagゲット。

考察

今回やって思ったのが、プログラムを組むのは絶対条件として、サイトやツールを用いることも大いに大切である。素因数分解はプログラムでは不可能に近い。文字に変換するのもプログラムでやったら一発なので、経験していきながら適切な方法を学んでいきたい。

The Numbers

The numbers... what do they mean?として画像が渡された。

{}があるので考えられるのは{の前がpicoCTFを表しているように思った。数字を文字に変換するコードさえわかれば後は変換するだけ。よくよく考えていたらCの位置に3がある。つまり、アルファベット順という可能性がある。対応させていったら終了。
(picoCTF2019 The Numbers [Cryptography])この人のwriteUpではツールが利用されていた。

caesar

Decrypt this message.と書かれていたpicoCTF{ynkooejcpdanqxeykjrbdofgkq}という文字が与えられている。一応入力。incorrectですよね。中身をシーザー暗号で復号すればいいと考え、(DenCode)を用いて復号した。可読できる文字列まで数値を変えて行い、それっぽいのが出てきたら終了。

13

Cryptography can be easy, do you know what ROT13 is? cvpbPGS{abg_gbb_onq_bs_n_ceboyrz}と書かれている。
ROT13はアルファベットを13順進めて変換させるものだと理解している。(DenCode)プログラムを組んでもいいと思いますが、ツールを使いました。修了。

interencdec

Can you get the real meaning from this file. Download the file here.
ファイルが与えられた。

└─# cat enc_flag
YidkM0JxZGtwQlRYdHFhR3g2YUhsZmF6TnFlVGwzWVROclgyZzBOMm8yYXpZNWZRPT0nCg==

どう見てもbase64っぽい。cyberchefにぶち込む。

ということでb``で囲まれた中にまたbase64である。そこを抽出してデコード。

flagっぽい形にはなったがまだ一工夫欲しているようだ。でも、この感じカエサル暗号だったかrot13のような感じに似ている気がする。rot13のRotate Number を19にするといい感じになった。終了。

Custom encryption

Can you get sense of this code file and write the function that will decode the given encrypted file content. Find the encrypted file here flag_info and code file might be good to analyze and get the flag.
ということで、特殊な暗号化を行うプログラムが渡されている。それを解読する。

from random import randint
import sys


def generator(g, x, p):
    return pow(g, x) % p

powはg^xした後にpで割り算した余りを返すようだ。

def encrypt(plaintext, key):
    cipher = []
    for char in plaintext:
        cipher.append(((ord(char) * key*311)))
    return cipher

(Pythonのord関数の使い方を現役エンジニアが解説【初心者向け】)を参考にすると、

ord関数とはPythonで文字をUnicode値に変換する関数です。

つまり、ord('a')=97, char(97) = aとなる。つまり、平文をUnicodeにして、それとkey*311をした数値列を返すようだ。

def is_prime(p):
    v = 0
    for i in range(2, p + 1):
        if p % i == 0:
            v = v + 1
    if v > 1:
        return False
    else:
        return True

素数判定かな。

def dynamic_xor_encrypt(plaintext, text_key):
    cipher_text = ""
    key_length = len(text_key)
    for i, char in enumerate(plaintext[::-1]):
        key_char = text_key[i % key_length]
        encrypted_char = chr(ord(char) ^ ord(key_char))
        cipher_text += encrypted_char
    return cipher_text

enumerateは(Python, enumerateの使い方: リストの要素とインデックスを取得)を参考にすると、要素とともにインデックスも与えてくれる関数。plaintext[::-1]は(Pythonにおける [::-1] と言うのはどう言う意味ですか？)を参考にすると、[start:stop:step]だそうなので、[::-1]は後ろから先頭までを逆順に全部出力することになる。text_keyから一文字取ってきて、それと平文のunicodeをべき乗する。それを文字に直して暗号文(cipher_text)を再構成する。

def test(plain_text, text_key):
    p = 97
    g = 31
    if not is_prime(p) and not is_prime(g):
        print("Enter prime numbers")
        return
    a = randint(p-10, p)
    b = randint(g-10, g)
    print(f"a = {a}")
    print(f"b = {b}")
    u = generator(g, a, p)
    v = generator(g, b, p)
    key = generator(v, a, p)
    b_key = generator(u, b, p)
    shared_key = None
    if key == b_key:
        shared_key = key
    else:
        print("Invalid key")
        return
    semi_cipher = dynamic_xor_encrypt(plain_text, text_key)
    cipher = encrypt(semi_cipher, shared_key)
    print(f'cipher is: {cipher}')

randint(a,b)は(Pythonでランダムな小数・整数を生成するrandom, randrange, randintなど)はa以上b以下の範囲の整数を返す。これで生成される乱数が与えられるa,bである。これkeyとb_keyは同じですよね。鍵交換を想定しているのかな？そのあとdynamic_xor_encryptとencryptして終了。

if __name__ == "__main__":
    message = sys.argv[1]
    test(message, "trudeau")

引数に平文を置き、text_keyは "trudeau"であるようだ。これを逆から計算できるようにして以下のコードとしたらflagゲット。

import sys

def decrypt(cipher,shared_key):
  semi_dec = ""
  for inte in cipher:
    semi_dec += (chr(int((inte/shared_key)/311)))
  return semi_dec

暗号化では掛け算されていたので割り算する。

def d_x_d(semi_dec, text_key):
  dec = ""
  key_length = len(text_key)

  for i, char in enumerate(semi_dec):
        key_char = text_key[i % key_length]
        flag = 0
        i=0
        while(flag ==0):
          if (i^ord(key_char) == ord(char)):
            decrypted_char = chr(i)
            flag =1
          else:
              i += 1
        dec = decrypted_char + dec
  return dec

べき乗の乗数と計算後の数値が与えられていたので、根を総当たりで求めた。

def generator(g, x, p):
    return pow(g, x) % p

a = 89
b = 27
text_key="trudeau"
cipher= [33588, 276168, 261240, 302292, 343344, 328416, 242580, 85836, 82104, 156744, 0, 309756, 78372, 18660, 253776, 0, 82104, 320952, 3732, 231384, 89568, 100764, 22392, 22392, 63444, 22392, 97032, 190332, 119424, 182868, 97032, 26124, 44784, 63444]
p = 97
g = 31
u = generator(g, a, p)
v = generator(g, b, p)
key = generator(v, a, p)
b_key = generator(u, b, p)
shared_key = None
if key == b_key:
     shared_key = key
else:
    print("Invalid key")
semi_dec = decrypt(cipher,shared_key)
plain = d_x_d(semi_dec, text_key)
print(plain)

として終了。

ここより下未解決

C3

This is the Custom Cyclical Cipher! Download the ciphertext here. Download the encoder here. Enclose the flag in our wrapper for submission. If the flag was "example" you would submit "picoCTF{example}".
ということで、これも先と同じ感じかな？プログラムと暗号文が渡された。

import sys
chars = ""
from fileinput import input
for line in input():
  chars += line

fileinputのinput()は(Python の fileinput モジュール便利)から引数のファイルから一行ずつ読み込む関数のようだ。つまり、最初の方はファイル読み込んだのをcharにつなげて一行にした感じ。

lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"

out = ""

何かしらを定義。

prev = 0
for char in chars:
  cur = lookup1.index(char)
  out += lookup2[(cur - prev) % 40]
  prev = cur

sys.stdout.write(out)

一行にした列から一文字ずつ取り出し、indexしている(Python 文字列の位置を取得する(find/index))。つまり、位置によって文字を数値に変えている。それに演算をした数値をlookup2のインデックスにしてそれが出力になる。prevは先のインデックスである。これを復号する。
一番最後の暗号化を考えたとき、lなので、最後の計算のoutはlになる。lookup2より31番目にある。つまり、(cur-prev)%40 =31である。これでcurを求めればファイルの最後の文字が分かるが、prevは前回のcurがないとわからない。機能的に最初のcurが分かるとどんどんわかる仕組みだと思った。%40があるのが気になる。(cur-prev)がマイナスになったときの処理と考えられる。以上のことを考えコードにすると以下になる。

cigher = "DLSeGAGDgBNJDQJDCFSFnRBIDjgHoDFCFtHDgJpiHtGDmMAQFnRBJKkBAsTMrsPSDDnEFCFtIbEDtDCIbFCFtHTJDKerFldbFObFCFtLBFkBAAAPFnRBJGEkerFlcPgKkImHnIlATJDKbTbFOkdNnsgbnJRMFnRBNAFkBAAAbrcbTKAkOgFpOgFpOpkBAAAAAAAiClFGIPFnRBaKliCgClFGtIBAAAAAAAOgGEkImHnIl"
lookup1 = "\n \"#()*+/1:=[]abcdefghijklmnopqrstuvwxyz"
lookup2 = "ABCDEFGHIJKLMNOPQRSTabcdefghijklmnopqrst"
dec = ""
prev = 0
for char in cigher:
  amari = lookup2.index(char)
  cur = amari + prev
  if (cur >= 40):
    cur = cur%40
  plain = lookup1[cur]
  dec +=plain
  prev = cur
print(dec)

実行すると

#asciiorder
#fortychars
#selfinput
#pythontwo

chars = ""
from fileinput import input
for line in input():
    chars += line
b = 1 / 1

for i in range(len(chars)):
    if i == b * b * b:
        print chars[i] #prints
        b += 1 / 1

何かしらのコードが出てきた。よくわからない。 writeUpを確認した( picoCTF 2024 - Writeup)。このコード自体を出力するコードが必要だったのですね。