RiK's Blog - RSA
type: channel
link: https://pwnerik.cn/tag/RSA/
items: 西电网安实验班 现代密码学 实验四
items: 西电网安实验班 现代密码学 实验三

西电网安实验班 现代密码学 实验四
type: item
date: 2025-12-09T07:54:00+00:00
description: RSA 加密体制破译来源：“RSA 大礼包”——首届（2016）全国高校密码数学挑战赛 赛题三截获数据处理首先按照赛题描述的帧结构提取所有的截获数据：1024bit 模数 N | 1024bit 加密指数 e | 1024bit 密文 m^e mod NFrame0: N = 90058705186558569935261948496132914380077312570281980020033760044382510933070450931241348678652103772768114420567119848142360867111065753301402088676701668212035175754850951897103338079978959810673297215370534716084813732883918187890434411552463739669878295417744080700424913250020348487161014643951785502867 e = 46786465362686334917265996843779843233606992585424976481745055335468678697948774988450305612127967926533923268260412557000125153569622340353246096040604284883505587337829322949633637609180797447754513992039018904786537115087888005528547900640339270052628915440787357271345416818313808448127098885767015748889 c = 48641173720475702278690317652676924796340996697567087705119344461991930773386153198223372579328462635803653561516674380209276666328375805315553713680858906705068657158073776194628700821011001144559278784795978097710145192236347629751116534400207288736776545247409895672030976932673010818369814246455196991083 -------- Frame1: N = 92921790800705826977497755832938592891062287903332844896046168726101016067456726822505517352409138948392871113192427210529297191908638888388136391240683157994654207338463678065440899870434887094216772312358731142317774259942199808535233769089985063860828267808621928898445383706310204223006136919334252875849 e = 65537 c = 1626661141529320283833484152716550848856697186049377493478368799832043379420727509223318694347625977694500761460048670101820769656612419734057871562023463159698522348510157125720014700549254630959391701883372400982386084212421115166791728704867253734354874934210987301137512341070190760227227749365878233484 -------- Frame2: N = 9025265360096445352455966929661813527291128977594919492254352087216414776865042103817633005359996860113582175067268566436078659543002868441941189331607428631279373082296356422056461670857376476438683012381819718323344347250610682891967040678522812487622…

西电网安实验班 现代密码学 实验三
type: item
date: 2025-11-25T11:01:00+00:00
description: 题目一Project Euler RSA Encryption Problem 182链接：https://projecteuler.net/problem=182RSA 有可能存在加密但没有加密的情况。起初遍历所有可能的消息并逐个加密来计算 unconsealed messages count。后来发现有以下公式：$$ N = (1 + \gcd(e-1, p-1)) \times (1 + \gcd(e-1, q-1)) $$from gmpy2 import gcd p = 1009 q = 3643 phi = (p - 1) * (q - 1) min_unconcealed = p * q candidates = [] for e in range(3, phi, 2): if gcd(e, phi) != 1: continue count = (1 + gcd(e - 1, p - 1)) * (1 + gcd(e - 1, q - 1)) if count < min_unconcealed: min_unconcealed = count candidates = [e] elif count == min_unconcealed: candidates.append(e) print(f"min_unconcealed: {min_unconcealed}") print("e:", end=" ") for e in candidates[:50]: print(f'{e} ', end='') print()题目二Implement RSA链接：https://www.cryptopals.com/sets/5/challenges/39只是实现一个简单的 RSA，要求手写 exgcd 和 modinv，那就手写吧。from gmpy2 import next_prime, powmod from secrets import randbits from Crypto.Util.number import bytes_to_long def gcd(a, b): while b != 0: a, b = b, a % b return a def ex_gcd(a, b): if b == 0: return 1, 0 else: x1, y1 = ex_gcd(b, a % b) x = y1 y = x1 - (a // b) * y1 return x, y def inverse(a, m): x, _ = ex_gcd(a, m) return (x % m + m) % m e = 3 while True: p = next_prime(randbits(64)) q = next_prime(randbits(64)) n = p * q phi = (p - 1) * (q - 1) if gcd(e, phi) == 1: break m = bytes_to_long(b'pwnerik.cn') assert 0 <= m < n c = powmod(m, e, n) d = inverse(e, phi) msg = powmod(c, d, n) assert m == msg这个实现有很多问题，例如 e、p、q 太小。