picoCTF_Mind your Ps and Qs 實戰解析

更新於 發佈於 閱讀時間約 2 分鐘

前言

這題主要是在考 RSA 加密演算法,為此我還特地去研究了費馬小定理、尤拉定理、RSA演算法證明,但也因此把自己弄得頭昏眼花。讓我們一起看看這困難的一題吧。

題述

  • linkpicoCTF - picoGym Challenges
  • Description:In RSA, a small e value can be problematic, but what about N? Can you decrypt this? values
  • hint:Bits are expensive, I used only a little bit over 100 to save money


把 values 下載下來後會長下面這樣

raw-image

c 為密文、n 和 e 為公鑰。要想拿到明文還需要私鑰(d),而要怎麼拿到私鑰呢?


開始解題

首先我們要了解RSA 的加密方式,如下:

raw-image
raw-image

C 是密文,M 是名文。

由第 5 點我們知道 d 可以利用逆模運算得到,而在 python 中逆模函數有兩種。

第一種inverse

想要用 inverse 需要先安裝它的套件,因此我們可以在 Terminal 中下這個指令。

raw-image

pip不行可以用pip3試試。

當我們引入 inverse 的函式庫後就可以使用了。

raw-image

inverse(2,3) 會等於 2 是因為2*2 mod 3 = 1

第二種pow

其實pow函式比較廣為人知的是他開次方的用法,不過,如果我們使用下列方法就可以變成逆模運算。

raw-image

最新版的 python 可以直接在pow中間加一個 -1 變成逆模運算。

萬事俱備只欠東風,而這個東風就是我們的𝜑。由算式中我們可以看到 e 乘 d 後是 mod 𝜑,而𝜑是由 (p-1)(q-1) 而來,又 N=p*q,所以只要我們分解出 p、q 就可以知道𝜑,就可以得到 d,就可以拿到 M,就可以解出 flag了(YA~)。

而 p、q 也有兩種分解方法。

第一種factordb.com

這是一個可以幫我們分解出質因數的網頁,不過,有時他也會有解不出來的時候需要看運氣。

第二種yafu

  • 下載解壓縮完
  • 點開 yafu-x64
  • 輸入 factor(要分解的數)
  • 點開 factor 文件檔就可以看到分解出來的數

不過,這個跑很慢,所以建議是第一種方法不行再試 yafu。

接著利用 python 拿到 flag,如下。

raw-image

倒數第二行是測試用不用理它。

最後一行的hex()是將 int 轉為16進制,bytes.fromhex()是將hex轉為bytes,而[2:]是因為hex()輸出的前兩個字是0x,0x是為了告訴電腦這是16進制。


耶~終於打完了。

聽說幫這篇按讚的話對發票都會中喔╰(*°▽°*)╯❤️


內容總結
picoCTF平台
5
/5
avatar-img
16會員
105內容數
有別於未付費的文章,專題區的文章偏向愛情短篇小說,較有戲劇性,篇幅也會較長;未付費文章會偏向極短篇小說,並且以類似散文的手法寫作
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
周濡墨的沙龍 的其他內容
題如其名,這題是在考我們知不知道 Tab 鍵在 Linux Terminal 中的作用。 所謂科技始於人性,Tab鍵的存在即是如此......
5/5picoCTF平台
今天會比較晚發文有一部分原因和這個有關@@,我絕對不會說另一部分原因是因為我整個下午都在睡覺和滑手機><。 其實,費馬小定理很好證,網路上也一堆教學,而 RSA 演算法只要知道尤拉定理也是小菜一疊,真正讓我頭疼的是尤拉定理的證明。 會這樣說是因為我有點自虐症,放著簡單的證明手法不用......
熱騰騰的文章又來囉~ 在開始之前想先聊聊為甚麼我想些 picoCTF 這系列的文章。 St
5/5picoCTF平台
本來打算是一天一題的,但前天興致高昂,一不小心就寫了兩題。 不過,也因為這兩題相對簡單,所以我才能完成這樣的任務。要知道在 picoCTF 平台裡,難的事非常難。我就曾經為了一題足足花了兩天才弄懂。 最後在開始之前和大家分享一個挑題的小技巧。
0/5picoCTF平台
感覺再不寫些甚麼筆就要開始生鏽了,以這樣的心情決定開啟 picoCTF writeup 系列。 也是因為最近生活過得平平淡淡,沒什麼值得和大家分享的,只好來寫寫我覺得有趣的 picoCTF題目 writeup。 這篇是這系列的第一篇。希望自己可以用簡顯易懂的方式帶著各位享受尋找寶藏(flag)
5/5picoCTF平台
題如其名,這題是在考我們知不知道 Tab 鍵在 Linux Terminal 中的作用。 所謂科技始於人性,Tab鍵的存在即是如此......
5/5picoCTF平台
今天會比較晚發文有一部分原因和這個有關@@,我絕對不會說另一部分原因是因為我整個下午都在睡覺和滑手機><。 其實,費馬小定理很好證,網路上也一堆教學,而 RSA 演算法只要知道尤拉定理也是小菜一疊,真正讓我頭疼的是尤拉定理的證明。 會這樣說是因為我有點自虐症,放著簡單的證明手法不用......
熱騰騰的文章又來囉~ 在開始之前想先聊聊為甚麼我想些 picoCTF 這系列的文章。 St
5/5picoCTF平台
本來打算是一天一題的,但前天興致高昂,一不小心就寫了兩題。 不過,也因為這兩題相對簡單,所以我才能完成這樣的任務。要知道在 picoCTF 平台裡,難的事非常難。我就曾經為了一題足足花了兩天才弄懂。 最後在開始之前和大家分享一個挑題的小技巧。
0/5picoCTF平台
感覺再不寫些甚麼筆就要開始生鏽了,以這樣的心情決定開啟 picoCTF writeup 系列。 也是因為最近生活過得平平淡淡,沒什麼值得和大家分享的,只好來寫寫我覺得有趣的 picoCTF題目 writeup。 這篇是這系列的第一篇。希望自己可以用簡顯易懂的方式帶著各位享受尋找寶藏(flag)
5/5picoCTF平台
你可能也想看
Google News 追蹤
Thumbnail
2025 年,從分享精彩的 #Myvocus2024 年度回顧開始! #Myvocus2024 年度回顧通知已送達 vocus 的 2024 有超過 12 萬筆訂單、35 萬則以上的內容、16 萬以上的新會員、4 千+ 筆數位商品訂單,5 萬 + 則貼文! 曬曬你的 2024 vocus 吧!
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
本篇文章分享了一些常見的數學陷阱題目,並提供瞭解答與相應的陷阱由來。
Thumbnail
演算法映射化簡的核心觀念 在面對新題目的時候,除了重頭想一個新的演算法之外; 還有另一個方法,想看看有沒有核心觀念彼此相同的問題與演算法, 如果有,就可以把新的題目映射化簡到已知解法的問題,用已知的演算法去解開。 接著,我們會介紹幾個範例,並且使用映射化簡的技巧來解題,透過化
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
解決電腦上遇到的問題、證明正確性、探討效率 並且很著重溝通,說服別人你做的事是正確且有效率的。 內容: 計算模型、資料結構介紹、演算法介紹、時間複雜度介紹。
Thumbnail
2025 年,從分享精彩的 #Myvocus2024 年度回顧開始! #Myvocus2024 年度回顧通知已送達 vocus 的 2024 有超過 12 萬筆訂單、35 萬則以上的內容、16 萬以上的新會員、4 千+ 筆數位商品訂單,5 萬 + 則貼文! 曬曬你的 2024 vocus 吧!
Thumbnail
嘿,大家新年快樂~ 新年大家都在做什麼呢? 跨年夜的我趕工製作某個外包設計案,在工作告一段落時趕上倒數。 然後和兩個小孩過了一個忙亂的元旦。在深夜時刻,看到朋友傳來的解籤網站,興致勃勃熬夜體驗了一下,覺得非常好玩,或許有人玩過了,但還是想寫上來分享紀錄一下~
Thumbnail
本篇文章分享了一些常見的數學陷阱題目,並提供瞭解答與相應的陷阱由來。
Thumbnail
演算法映射化簡的核心觀念 在面對新題目的時候,除了重頭想一個新的演算法之外; 還有另一個方法,想看看有沒有核心觀念彼此相同的問題與演算法, 如果有,就可以把新的題目映射化簡到已知解法的問題,用已知的演算法去解開。 接著,我們會介紹幾個範例,並且使用映射化簡的技巧來解題,透過化
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
解決電腦上遇到的問題、證明正確性、探討效率 並且很著重溝通,說服別人你做的事是正確且有效率的。 內容: 計算模型、資料結構介紹、演算法介紹、時間複雜度介紹。