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進制。


耶~終於打完了。

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


留言
avatar-img
留言分享你的想法!
avatar-img
周濡墨的沙龍
17會員
112內容數
有別於未付費的文章,專題區的文章偏向愛情短篇小說,較有戲劇性,篇幅也會較長;未付費文章會偏向極短篇小說,並且以類似散文的手法寫作
周濡墨的沙龍的其他內容
2025/04/23
核心意識 自有平台 工作地點 職缺和實習 培訓 你不需要很厲害 QA 面試詳細內容:20分鐘線上程式測驗。沒有複試,一次面試。會從履歷中問問題 有沒有短期實習,例如暑期實習:希望暑假+一個學期。開學後每周三天沒有硬性規定哪幾天 資安推薦能力或證照:英文能力,e
Thumbnail
2025/04/23
核心意識 自有平台 工作地點 職缺和實習 培訓 你不需要很厲害 QA 面試詳細內容:20分鐘線上程式測驗。沒有複試,一次面試。會從履歷中問問題 有沒有短期實習,例如暑期實習:希望暑假+一個學期。開學後每周三天沒有硬性規定哪幾天 資安推薦能力或證照:英文能力,e
Thumbnail
2025/03/03
此題為栅欄密碼或稱籬笆密碼。會知道栅欄密碼是因為文字中出現fence和zig-zag pattern。其中第二點很符合栅欄密碼的特徵,請看下圖。 栅欄密碼真就是以Z字形進行加密的。 而這題只要放進隨便一個online decrypt tool都可以解出來。例如我就是用這個網站解出來的。欄數填
Thumbnail
2025/03/03
此題為栅欄密碼或稱籬笆密碼。會知道栅欄密碼是因為文字中出現fence和zig-zag pattern。其中第二點很符合栅欄密碼的特徵,請看下圖。 栅欄密碼真就是以Z字形進行加密的。 而這題只要放進隨便一個online decrypt tool都可以解出來。例如我就是用這個網站解出來的。欄數填
Thumbnail
2025/01/29
介紹 Remedy ctf 裡,solidity(區塊鏈)的題目占多數。並且在比賽中會不時新增題目 學到知識 雖然沒有解出一題(除了第一題水題),但還是學到一些東西。 先來介紹一些專有名詞 RPC 客戶和區塊鏈互動的介面。如果用瀏覽器造訪會得到一個json,像這樣{"detail":
Thumbnail
2025/01/29
介紹 Remedy ctf 裡,solidity(區塊鏈)的題目占多數。並且在比賽中會不時新增題目 學到知識 雖然沒有解出一題(除了第一題水題),但還是學到一些東西。 先來介紹一些專有名詞 RPC 客戶和區塊鏈互動的介面。如果用瀏覽器造訪會得到一個json,像這樣{"detail":
Thumbnail
看更多
你可能也想看
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
孩子寫功課時瞇眼?小心近視!這款喜光全光譜TIONE⁺光健康智慧檯燈,獲眼科院長推薦,網路好評不斷!全光譜LED、180cm大照明範圍、5段亮度及色溫調整、350度萬向旋轉,讓孩子學習更舒適、保護眼睛!
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
分享一個猜數字的遊戲題目,給予提示讓玩家找出正確的四位數密碼。
Thumbnail
本篇文章分享了一些常見的數學陷阱題目,並提供瞭解答與相應的陷阱由來。
Thumbnail
本篇文章分享了一些常見的數學陷阱題目,並提供瞭解答與相應的陷阱由來。
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
Leetcode 精選75題 題目與題解 熱門考點 目錄 (持續更新中) 建議從左側目錄 或者 按Ctrl+F輸入關鍵字進行搜尋
Thumbnail
題目給定一個布林代數的二元樹,要求我們計算最後的結果。 葉子節點都是真假值 非葉子節點都是布林運算子
Thumbnail
題目給定一個布林代數的二元樹,要求我們計算最後的結果。 葉子節點都是真假值 非葉子節點都是布林運算子
Thumbnail
這題主要是在考 RSA 加密演算法,為此我還特地去研究了費馬小定理、尤拉定理、RSA演算法證明,但也因此把自己弄得頭昏眼花。讓我們一起看看這困難的一題吧。
Thumbnail
這題主要是在考 RSA 加密演算法,為此我還特地去研究了費馬小定理、尤拉定理、RSA演算法證明,但也因此把自己弄得頭昏眼花。讓我們一起看看這困難的一題吧。
Thumbnail
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
題目敘述 輸入給定一個鏈結串列的head node。 要求我們進行化簡,只要某個節點的右手邊存在比較大的節點,就刪除掉。 例如 5->2->13->3 5的右手邊有13,所以5刪除掉。 2的右手邊有13,所以2刪除掉。 13的右手邊沒有更大的節點,所以13留著。 3的右手邊沒有更大
Thumbnail
最近會試著寫一些統整類的文章, 幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。 找零錢框架 在以前學過的題目中,我們已經學會了考零錢的抽象思考邏輯與框架,就是試著用每一種銅板去湊出n元(也就是找零錢的過程) 寫成虛擬碼或演算法,找零錢用了幾枚銅板可以這樣表達 # 銅板數目累加​
Thumbnail
最近會試著寫一些統整類的文章, 幫助讀者、觀眾整理、吸收、複習已經學習到的演算法框架。 找零錢框架 在以前學過的題目中,我們已經學會了考零錢的抽象思考邏輯與框架,就是試著用每一種銅板去湊出n元(也就是找零錢的過程) 寫成虛擬碼或演算法,找零錢用了幾枚銅板可以這樣表達 # 銅板數目累加​
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
題目敘述 題目會給定一個輸入字串s和一套編碼規則,要求我們針對字串s進行解碼,並且以字串的形式返回答案。 編碼規則: 數字[字串] -> []內的字串以對應倍數做展開,而且允許巢狀編碼。 例如: 3[a] 解碼完就是 aaa 2[bc] 解碼完就是 bcbc 2[a2[b]] = 2
Thumbnail
給你一堆字母請你湊出單字,Scramble 貌似也是這樣玩的 (?
Thumbnail
給你一堆字母請你湊出單字,Scramble 貌似也是這樣玩的 (?
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News