1896 lines
136 KiB
HTML
1896 lines
136 KiB
HTML
<!DOCTYPE HTML>
|
||
<html lang="en" class="coal" dir="ltr">
|
||
<head>
|
||
<!-- Book generated using mdBook -->
|
||
<meta charset="UTF-8">
|
||
<title>Rsa attack - Andrew's Blog</title>
|
||
|
||
|
||
<!-- Custom HTML head -->
|
||
|
||
<meta name="description" content="Andrew Ryan's Blog">
|
||
<meta name="viewport" content="width=device-width, initial-scale=1">
|
||
<meta name="theme-color" content="#ffffff">
|
||
|
||
<link rel="icon" href="../../favicon.svg">
|
||
<link rel="shortcut icon" href="../../favicon.png">
|
||
<link rel="stylesheet" href="../../css/variables.css">
|
||
<link rel="stylesheet" href="../../css/general.css">
|
||
<link rel="stylesheet" href="../../css/chrome.css">
|
||
|
||
<!-- Fonts -->
|
||
<link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
|
||
<link rel="stylesheet" href="../../fonts/fonts.css">
|
||
|
||
<!-- Highlight.js Stylesheets -->
|
||
<link rel="stylesheet" href="../../highlight.css">
|
||
<link rel="stylesheet" href="../../tomorrow-night.css">
|
||
<link rel="stylesheet" href="../../ayu-highlight.css">
|
||
|
||
<!-- Custom theme stylesheets -->
|
||
<link rel="stylesheet" href="../../src/style/custom.css">
|
||
|
||
<!-- MathJax -->
|
||
<script async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
|
||
</head>
|
||
<body class="sidebar-visible no-js">
|
||
<div id="body-container">
|
||
<!-- Provide site root to javascript -->
|
||
<script>
|
||
var path_to_root = "../../";
|
||
var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "coal" : "coal";
|
||
</script>
|
||
|
||
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
||
<script>
|
||
try {
|
||
var theme = localStorage.getItem('mdbook-theme');
|
||
var sidebar = localStorage.getItem('mdbook-sidebar');
|
||
|
||
if (theme.startsWith('"') && theme.endsWith('"')) {
|
||
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
||
}
|
||
|
||
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
||
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
||
}
|
||
} catch (e) { }
|
||
</script>
|
||
|
||
<!-- Set the theme before any content is loaded, prevents flash -->
|
||
<script>
|
||
var theme;
|
||
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
||
if (theme === null || theme === undefined) { theme = default_theme; }
|
||
var html = document.querySelector('html');
|
||
html.classList.remove('coal')
|
||
html.classList.add(theme);
|
||
var body = document.querySelector('body');
|
||
body.classList.remove('no-js')
|
||
body.classList.add('js');
|
||
</script>
|
||
|
||
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
|
||
|
||
<!-- Hide / unhide sidebar before it is displayed -->
|
||
<script>
|
||
var body = document.querySelector('body');
|
||
var sidebar = null;
|
||
var sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
|
||
if (document.body.clientWidth >= 1080) {
|
||
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
||
sidebar = sidebar || 'visible';
|
||
} else {
|
||
sidebar = 'hidden';
|
||
}
|
||
sidebar_toggle.checked = sidebar === 'visible';
|
||
body.classList.remove('sidebar-visible');
|
||
body.classList.add("sidebar-" + sidebar);
|
||
</script>
|
||
|
||
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
||
<div class="sidebar-scrollbox">
|
||
<ol class="chapter"><li class="chapter-item affix "><a href="../../index.html">Andrew's Blog</a></li><li class="chapter-item "><a href="../../posts/linux/linux.html"><strong aria-hidden="true">1.</strong> linux</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/linux/install_linux.html"><strong aria-hidden="true">1.1.</strong> install linux</a></li><li class="chapter-item "><a href="../../posts/linux/bash_profile.html"><strong aria-hidden="true">1.2.</strong> bash profile</a></li><li class="chapter-item "><a href="../../posts/linux/command_list.html"><strong aria-hidden="true">1.3.</strong> command list</a></li><li class="chapter-item "><a href="../../posts/linux/git_guide.html"><strong aria-hidden="true">1.4.</strong> git guide</a></li><li class="chapter-item "><a href="../../posts/linux/tar.html"><strong aria-hidden="true">1.5.</strong> tar</a></li><li class="chapter-item "><a href="../../posts/linux/run_x86_elf_in_x64_setup.html"><strong aria-hidden="true">1.6.</strong> run x86 elf in x64 setup</a></li></ol></li><li class="chapter-item "><a href="../../posts/mac/mac.html"><strong aria-hidden="true">2.</strong> mac</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/mac/macos_profiles.html"><strong aria-hidden="true">2.1.</strong> macos profiles</a></li></ol></li><li class="chapter-item "><a href="../../posts/swift/swift.html"><strong aria-hidden="true">3.</strong> swift</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/swift/learn_swift.html"><strong aria-hidden="true">3.1.</strong> learn swift basics</a></li><li class="chapter-item "><a href="../../posts/swift/swift_extensions.html"><strong aria-hidden="true">3.2.</strong> Swift extensions</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_extension.html"><strong aria-hidden="true">3.3.</strong> SwiftUI extensions</a></li><li class="chapter-item "><a href="../../posts/swift/install_swift.html"><strong aria-hidden="true">3.4.</strong> install swift</a></li><li class="chapter-item "><a href="../../posts/swift/task_planner.html"><strong aria-hidden="true">3.5.</strong> implment task panner app with SwiftUI</a></li><li class="chapter-item "><a href="../../posts/swift/swift_cheat_sheet.html"><strong aria-hidden="true">3.6.</strong> Swift Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/swift/yinci_url.html"><strong aria-hidden="true">3.7.</strong> Personal privacy protocol</a></li><li class="chapter-item "><a href="../../posts/swift/swift_regular_exressions.html"><strong aria-hidden="true">3.8.</strong> Swift regular exressions</a></li><li class="chapter-item "><a href="../../posts/ios/how_to_create_beautiful_ios_charts_in_swift.html"><strong aria-hidden="true">3.9.</strong> How to Create Beautiful iOS Charts in鑱絊wift</a></li><li class="chapter-item "><a href="../../posts/swift/swiftui_source_code.html"><strong aria-hidden="true">3.10.</strong> SwiftUI source code</a></li><li class="chapter-item "><a href="../../posts/swift/use_swift_fetch_iciba_api.html"><strong aria-hidden="true">3.11.</strong> use swift fetch iciba API</a></li></ol></li><li class="chapter-item "><a href="../../posts/ios/ios.html"><strong aria-hidden="true">4.</strong> ios</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ios/cocaposd_setup_and_install_for_ios_project.html"><strong aria-hidden="true">4.1.</strong> cocaposd setup and install for ios project</a></li><li class="chapter-item "><a href="../../posts/ios/swiftui_show_gif_image.html"><strong aria-hidden="true">4.2.</strong> SwiftUI show gif image</a></li><li class="chapter-item "><a href="../../posts/ios/implement_task_planner_app.html"><strong aria-hidden="true">4.3.</strong> implement Task planner App</a></li></ol></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c.html"><strong aria-hidden="true">5.</strong> objective_c</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/objective_c/objective_c_cheat_sheet.html"><strong aria-hidden="true">5.1.</strong> Objective-C Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/objective_c/objective_c_for_absolute_beginners_read_note.html"><strong aria-hidden="true">5.2.</strong> Objective-C Note</a></li></ol></li><li class="chapter-item "><a href="../../posts/dart/dart.html"><strong aria-hidden="true">6.</strong> dart</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/dart/flutter.html"><strong aria-hidden="true">6.1.</strong> Flutter Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/dart/dart_cheat_sheet.html"><strong aria-hidden="true">6.2.</strong> Dart Cheat Sheet</a></li><li class="chapter-item "><a href="../../posts/flutter/flutter_dev_test.html"><strong aria-hidden="true">6.3.</strong> Flutter dev test</a></li></ol></li><li class="chapter-item "><a href="../../posts/rust/rust.html"><strong aria-hidden="true">7.</strong> rust</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/rust/offline_use_rust.html"><strong aria-hidden="true">7.1.</strong> Offline use rust</a></li><li class="chapter-item "><a href="../../posts/rust/rust_grammer.html"><strong aria-hidden="true">7.2.</strong> rust grammar</a></li><li class="chapter-item "><a href="../../posts/rust/pase_string_and_decimal_conversion.html"><strong aria-hidden="true">7.3.</strong> pase string and decimal conversion</a></li><li class="chapter-item "><a href="../../posts/rust/parse_types.html"><strong aria-hidden="true">7.4.</strong> rust types</a></li><li class="chapter-item "><a href="../../posts/rust/rust_life_cycle.html"><strong aria-hidden="true">7.5.</strong> Rust life cycle</a></li><li class="chapter-item "><a href="../../posts/rust/rust_generic.html"><strong aria-hidden="true">7.6.</strong> rust generics</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implment_matrix.html"><strong aria-hidden="true">7.7.</strong> Rust implement matrix</a></li><li class="chapter-item "><a href="../../posts/rust/rust_sort.html"><strong aria-hidden="true">7.8.</strong> Rust implement sort algorithms</a></li><li class="chapter-item "><a href="../../posts/rust/implement_aes_encryption.html"><strong aria-hidden="true">7.9.</strong> Rust implement AEC encryption and decryption</a></li><li class="chapter-item "><a href="../../posts/rust/implement_trie_data_structure.html"><strong aria-hidden="true">7.10.</strong> implement trie data structure</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_tree.html"><strong aria-hidden="true">7.11.</strong> implement tree data_structure</a></li><li class="chapter-item "><a href="../../posts/rust/list_dir.html"><strong aria-hidden="true">7.12.</strong> list dir</a></li><li class="chapter-item "><a href="../../posts/rust/fast_way_to_implment_object_trait.html"><strong aria-hidden="true">7.13.</strong> fast way to implment object trait</a></li><li class="chapter-item "><a href="../../posts/rust/compress_rust_binary_size.html"><strong aria-hidden="true">7.14.</strong> compress rust binary size</a></li><li class="chapter-item "><a href="../../posts/rust/implment_file_upload_backend.html"><strong aria-hidden="true">7.15.</strong> impliment file upload</a></li><li class="chapter-item "><a href="../../posts/rust/this_is_add_post_cli_implementation_in_rust.html"><strong aria-hidden="true">7.16.</strong> this is add_post cli implementation in rust</a></li><li class="chapter-item "><a href="../../posts/rust/use_rust_implment_a_copyclipbord_cli.html"><strong aria-hidden="true">7.17.</strong> Use rust implment a copyclipbord CLI</a></li><li class="chapter-item "><a href="../../posts/rust/sqlite_database_add_delete_update_show_in_rust.html"><strong aria-hidden="true">7.18.</strong> sqlite database add delete update show in rust</a></li><li class="chapter-item "><a href="../../posts/rust/implementing_tokio_joinhandle_for_wasm.html"><strong aria-hidden="true">7.19.</strong> Implementing tokio JoinHandle for wasm</a></li><li class="chapter-item "><a href="../../posts/rust/rust_implement_a_crate_for_encode_and_decode_brainfuck_and_ook.html"><strong aria-hidden="true">7.20.</strong> rust implement a crate for encode and decode brainfuck and ook</a></li><li class="chapter-item "><a href="../../posts/rust/slint_builtin_elements.html"><strong aria-hidden="true">7.21.</strong> Slint Builtin Elements</a></li><li class="chapter-item "><a href="../../posts/rust/corporate_network_install_rust_on_windows.html"><strong aria-hidden="true">7.22.</strong> Corporate network install Rust on windows</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_file_how_to_judge_static_link_or_dynamic_link_in_macos.html"><strong aria-hidden="true">7.23.</strong> rust binary file how to judge static link or dynamic link in Macos</a></li><li class="chapter-item "><a href="../../posts/rust/rust_binary_include_dir_and_get_contents.html"><strong aria-hidden="true">7.24.</strong> rust binary include dir and get contents</a></li><li class="chapter-item "><a href="../../posts/rust/rust_logger_non-block.html"><strong aria-hidden="true">7.25.</strong> rust logger non-block</a></li><li class="chapter-item "><a href="../../posts/rust/rust_connect_sql_server_database.html"><strong aria-hidden="true">7.26.</strong> rust connect sql server database</a></li><li class="chapter-item "><a href="../../posts/rust/rust_websocket_implment.html"><strong aria-hidden="true">7.27.</strong> rust websocket implment</a></li></ol></li><li class="chapter-item "><a href="../../posts/java/java.html"><strong aria-hidden="true">8.</strong> java</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/java/java_grammar.html"><strong aria-hidden="true">8.1.</strong> java grammar and codewar</a></li><li class="chapter-item "><a href="../../posts/java/run_jar.html"><strong aria-hidden="true">8.2.</strong> java run .jar</a></li><li class="chapter-item "><a href="../../posts/java/java_pomxml_add_defaultgoal_to_build.html"><strong aria-hidden="true">8.3.</strong> Java pomxml add defaultGoal to build</a></li><li class="chapter-item "><a href="../../posts/java/java_set_mvn_mirror.html"><strong aria-hidden="true">8.4.</strong> Java set mvn mirror</a></li></ol></li><li class="chapter-item "><a href="../../posts/python/python.html"><strong aria-hidden="true">9.</strong> python</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/python/convert_pesn.html"><strong aria-hidden="true">9.1.</strong> convert pesn</a></li><li class="chapter-item "><a href="../../posts/python/find_remove_dir.html"><strong aria-hidden="true">9.2.</strong> find and remove dir</a></li><li class="chapter-item "><a href="../../posts/python/timing_message.html"><strong aria-hidden="true">9.3.</strong> wechat send message</a></li><li class="chapter-item "><a href="../../posts/python/use_python_openpyxl_package_read_and_edit_excel_files.html"><strong aria-hidden="true">9.4.</strong> Use python openpyxl package read and edit excel files</a></li></ol></li><li class="chapter-item "><a href="../../posts/go/go.html"><strong aria-hidden="true">10.</strong> go</a></li><li class="chapter-item "><a href="../../posts/js/js.html"><strong aria-hidden="true">11.</strong> js</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/js/js_tutorial.html"><strong aria-hidden="true">11.1.</strong> js tutorial</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_map.html"><strong aria-hidden="true">11.2.</strong> ja map</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_math.html"><strong aria-hidden="true">11.3.</strong> js math</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_object.html"><strong aria-hidden="true">11.4.</strong> js object</a></li><li class="chapter-item "><a href="../../posts/js/js_tutorial_set.html"><strong aria-hidden="true">11.5.</strong> js set</a></li><li class="chapter-item "><a href="../../posts/js/single_thread_and_asynchronous.html"><strong aria-hidden="true">11.6.</strong> single thread and asynchronous</a></li><li class="chapter-item "><a href="../../posts/js/this.html"><strong aria-hidden="true">11.7.</strong> js this</a></li><li class="chapter-item "><a href="../../posts/js/js_implment_aes.html"><strong aria-hidden="true">11.8.</strong> js implment aes</a></li><li class="chapter-item "><a href="../../posts/js/getting_started_with_ajax.html"><strong aria-hidden="true">11.9.</strong> getting started with ajax</a></li><li class="chapter-item "><a href="../../posts/js/BinarySearchTree.html"><strong aria-hidden="true">11.10.</strong> binary search tree</a></li><li class="chapter-item "><a href="../../posts/js/goole_zx.html"><strong aria-hidden="true">11.11.</strong> goole zx</a></li><li class="chapter-item "><a href="../../posts/js/es6.html"><strong aria-hidden="true">11.12.</strong> es6</a></li></ol></li><li class="chapter-item "><a href="../../posts/ruby/ruby.html"><strong aria-hidden="true">12.</strong> ruby</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ruby/rails_setup_env.html"><strong aria-hidden="true">12.1.</strong> ruby on rails setup environment</a></li><li class="chapter-item "><a href="../../posts/ruby/learn_ruby.html"><strong aria-hidden="true">12.2.</strong> learn ruby</a></li><li class="chapter-item "><a href="../../posts/ruby/ruby_note.html"><strong aria-hidden="true">12.3.</strong> Ruby Note</a></li><li class="chapter-item "><a href="../../posts/ruby/setup_ruby_for_ctf.html"><strong aria-hidden="true">12.4.</strong> Setup ruby for CTF</a></li></ol></li><li class="chapter-item "><a href="../../posts/react/react.html"><strong aria-hidden="true">13.</strong> react</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/react/react_life_cycle.html"><strong aria-hidden="true">13.1.</strong> react life cycle</a></li><li class="chapter-item "><a href="../../posts/react/react_router.html"><strong aria-hidden="true">13.2.</strong> react router</a></li><li class="chapter-item "><a href="../../posts/react/react_this.html"><strong aria-hidden="true">13.3.</strong> react this</a></li><li class="chapter-item "><a href="../../posts/react/react_interviw.html"><strong aria-hidden="true">13.4.</strong> react interview</a></li><li class="chapter-item "><a href="../../posts/react/important_react_interview.html"><strong aria-hidden="true">13.5.</strong> important react interview</a></li><li class="chapter-item "><a href="../../posts/react/react_quick_reference.html"><strong aria-hidden="true">13.6.</strong> react quick reference</a></li><li class="chapter-item "><a href="../../posts/react/redux_quick_reference.html"><strong aria-hidden="true">13.7.</strong> redux quick reference</a></li></ol></li><li class="chapter-item "><a href="../../posts/vue/vue.html"><strong aria-hidden="true">14.</strong> vue</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/vue/vue_ajax.html"><strong aria-hidden="true">14.1.</strong> vue ajax</a></li></ol></li><li class="chapter-item "><a href="../../posts/angular/angular.html"><strong aria-hidden="true">15.</strong> angular</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/angular/controller_communication.html"><strong aria-hidden="true">15.1.</strong> controller communication</a></li><li class="chapter-item "><a href="../../posts/angular/creating_custom_directives.html"><strong aria-hidden="true">15.2.</strong> creating custom directives</a></li><li class="chapter-item "><a href="../../posts/angular/directive_notes.html"><strong aria-hidden="true">15.3.</strong> directive notes</a></li><li class="chapter-item "><a href="../../posts/angular/directive_communication.html"><strong aria-hidden="true">15.4.</strong> directive communication</a></li><li class="chapter-item "><a href="../../posts/angular/post_params.html"><strong aria-hidden="true">15.5.</strong> post params</a></li><li class="chapter-item "><a href="../../posts/angular/read_json_angular.html"><strong aria-hidden="true">15.6.</strong> read json angular</a></li><li class="chapter-item "><a href="../../posts/angular/same_route_reload.html"><strong aria-hidden="true">15.7.</strong> same route reload</a></li></ol></li><li class="chapter-item "><a href="../../posts/css/css.html"><strong aria-hidden="true">16.</strong> css</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/css/use_css_media.html"><strong aria-hidden="true">16.1.</strong> use css media</a></li></ol></li><li class="chapter-item "><a href="../../posts/php/php.html"><strong aria-hidden="true">17.</strong> php</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/php/for_php_string_implment_some_extemtion_functions.html"><strong aria-hidden="true">17.1.</strong> for php string implment some extemtion functions</a></li><li class="chapter-item "><a href="../../posts/php/php_cheatsheet.html"><strong aria-hidden="true">17.2.</strong> PHP cheatsheet</a></li></ol></li><li class="chapter-item "><a href="../../posts/leetcode/leetcode.html"><strong aria-hidden="true">18.</strong> leetcode</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/leetcode/rust_leetcode.html"><strong aria-hidden="true">18.1.</strong> rust leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_codewar.html"><strong aria-hidden="true">18.2.</strong> rust codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/swift_codewar.html"><strong aria-hidden="true">18.3.</strong> swift codewar</a></li><li class="chapter-item "><a href="../../posts/leetcode/js_leetcode.html"><strong aria-hidden="true">18.4.</strong> js leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/java_leetcode.html"><strong aria-hidden="true">18.5.</strong> java leetcode</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_huawei.html"><strong aria-hidden="true">18.6.</strong> huawei test</a></li><li class="chapter-item "><a href="../../posts/leetcode/rust_utils.html"><strong aria-hidden="true">18.7.</strong> rust common functions</a></li><li class="chapter-item "><a href="../../posts/leetcode/olympiad_training.html"><strong aria-hidden="true">18.8.</strong> Computer olympiad training</a></li></ol></li><li class="chapter-item expanded "><a href="../../posts/ctf/CTF.html"><strong aria-hidden="true">19.</strong> ctf</a><a class="toggle"><div>❱</div></a></li><li><ol class="section"><li class="chapter-item "><a href="../../posts/ctf/CTF_Note.html"><strong aria-hidden="true">19.1.</strong> CTF Note</a></li><li class="chapter-item "><a href="../../posts/ctf/0.1_Web.html"><strong aria-hidden="true">19.2.</strong> Web</a></li><li class="chapter-item "><a href="../../posts/ctf/4.1_Misc.html"><strong aria-hidden="true">19.3.</strong> Misc</a></li><li class="chapter-item "><a href="../../posts/ctf/3.2_PWN_note.html"><strong aria-hidden="true">19.4.</strong> PWN</a></li><li class="chapter-item "><a href="../../posts/ctf/3.1_Crypto.html"><strong aria-hidden="true">19.5.</strong> Crypto</a></li><li class="chapter-item expanded "><a href="../../posts/ctf/3.4_RSA_note.html" class="active"><strong aria-hidden="true">19.6.</strong> Rsa attack</a></li><li class="chapter-item "><a href="../../posts/ctf/3.5_Base64.html"><strong aria-hidden="true">19.7.</strong> Base64</a></li><li class="chapter-item "><a href="../../posts/ctf/0.0_SQL Injection Cheatsheet.html"><strong aria-hidden="true">19.8.</strong> SQL Injection Cheatsheet</a></li><li class="chapter-item "><a href="../../posts/ctf/1.1_SQL_injection.html"><strong aria-hidden="true">19.9.</strong> SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.2_SQL_injection_UNION_attacks.html"><strong aria-hidden="true">19.10.</strong> SQL Injection UNION attacks</a></li><li class="chapter-item "><a href="../../posts/ctf/1.3_Blind SQL injection.html"><strong aria-hidden="true">19.11.</strong> Blind SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.4_Code Injection.html"><strong aria-hidden="true">19.12.</strong> Code Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.5_SSRF.html"><strong aria-hidden="true">19.13.</strong> SSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.6_OS command injection.html"><strong aria-hidden="true">19.14.</strong> OS command injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.7_Local file inclusion.html"><strong aria-hidden="true">19.15.</strong> Local file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.8_Remote file inclusion.html"><strong aria-hidden="true">19.16.</strong> Remote file inclusion</a></li><li class="chapter-item "><a href="../../posts/ctf/1.9_CSRFm.html"><strong aria-hidden="true">19.17.</strong> CSRF</a></li><li class="chapter-item "><a href="../../posts/ctf/1.10_NoSQL injection.html"><strong aria-hidden="true">19.18.</strong> NoSQL injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.11_JSON injection.html"><strong aria-hidden="true">19.19.</strong> JSON injection</a></li><li class="chapter-item "><a href="../../posts/ctf/1.12_CTF_Web_SQL_Note.html"><strong aria-hidden="true">19.20.</strong> CTF Web SQL Note</a></li><li class="chapter-item "><a href="../../posts/ctf/2.1_XXE.html"><strong aria-hidden="true">19.21.</strong> XXE</a></li><li class="chapter-item "><a href="../../posts/ctf/2.2_XSS.html"><strong aria-hidden="true">19.22.</strong> XSS</a></li><li class="chapter-item "><a href="../../posts/ctf/2.3_Upload File.html"><strong aria-hidden="true">19.23.</strong> Upload File</a></li><li class="chapter-item "><a href="../../posts/ctf/2.4_serialize_unserialize.html"><strong aria-hidden="true">19.24.</strong> serialize unserialize</a></li><li class="chapter-item "><a href="../../posts/ctf/2.5_Race condition.html"><strong aria-hidden="true">19.25.</strong> Race condition</a></li><li class="chapter-item "><a href="../../posts/ctf/3.2_PWN_note.html"><strong aria-hidden="true">19.26.</strong> PWN_note</a></li><li class="chapter-item "><a href="../../posts/ctf/3.3_pwn HCTF2016 brop.html"><strong aria-hidden="true">19.27.</strong> pwn HCTF2016 brop</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_patch_defense_skill.html"><strong aria-hidden="true">19.28.</strong> PWN Patch defense skill</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_stack_overflow.html"><strong aria-hidden="true">19.29.</strong> PWN stack overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_heap_overflow.html"><strong aria-hidden="true">19.30.</strong> PWN heap overflow</a></li><li class="chapter-item "><a href="../../posts/ctf/pwn_format_string_vulnerability.html"><strong aria-hidden="true">19.31.</strong> PWN Format String Vulnerability</a></li><li class="chapter-item "><a href="../../posts/ctf/kali_linux_tutorials.html"><strong aria-hidden="true">19.32.</strong> Kali linux tutorials</a></li><li class="chapter-item "><a href="../../posts/ctf/google_dorks_2023_lists.html"><strong aria-hidden="true">19.33.</strong> Google Dorks 2023 Lists</a></li><li class="chapter-item "><a href="../../posts/ctf/dvwa_writeup.html"><strong aria-hidden="true">19.34.</strong> DVWA WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/bwapp_writeup.html"><strong aria-hidden="true">19.35.</strong> bWAPP WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/sqlilabs_writeup.html"><strong aria-hidden="true">19.36.</strong> sqlilabs WriteUp</a></li><li class="chapter-item "><a href="../../posts/ctf/ctf_train_at_hangzhou.html"><strong aria-hidden="true">19.37.</strong> ctf train at hangzhou</a></li><li class="chapter-item "><a href="../../posts/ctf/ctf_common_mindmap_list.html"><strong aria-hidden="true">19.38.</strong> ctf common mindmap list</a></li><li class="chapter-item "><a href="../../posts/ctf/error_based_sql_injection.html"><strong aria-hidden="true">19.39.</strong> Error Based SQL Injection</a></li><li class="chapter-item "><a href="../../posts/ctf/urlfinder_tutorial.html"><strong aria-hidden="true">19.40.</strong> URLFinder Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/observer_ward_tutorial.html"><strong aria-hidden="true">19.41.</strong> observer_ward Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/mysql_udf_.html"><strong aria-hidden="true">19.42.</strong> MySQL UDF 提权</a></li><li class="chapter-item "><a href="../../posts/ctf/nuclei__tutorial.html"><strong aria-hidden="true">19.43.</strong> Nuclei Tutorial</a></li><li class="chapter-item "><a href="../../posts/ctf/2024_ctf_solution_thinking.html"><strong aria-hidden="true">19.44.</strong> 2024 ctf solution thinking</a></li><li class="chapter-item "><a href="../../posts/ctf/man_che_si_te_bian_ma.html"><strong aria-hidden="true">19.45.</strong> 曼彻斯特编码</a></li></ol></li></ol>
|
||
</div>
|
||
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
|
||
<div class="sidebar-resize-indicator"></div>
|
||
</div>
|
||
</nav>
|
||
|
||
<!-- Track and set sidebar scroll position -->
|
||
<script>
|
||
var sidebarScrollbox = document.querySelector('#sidebar .sidebar-scrollbox');
|
||
sidebarScrollbox.addEventListener('click', function(e) {
|
||
if (e.target.tagName === 'A') {
|
||
sessionStorage.setItem('sidebar-scroll', sidebarScrollbox.scrollTop);
|
||
}
|
||
}, { passive: true });
|
||
var sidebarScrollTop = sessionStorage.getItem('sidebar-scroll');
|
||
sessionStorage.removeItem('sidebar-scroll');
|
||
if (sidebarScrollTop) {
|
||
// preserve sidebar scroll position when navigating via links within sidebar
|
||
sidebarScrollbox.scrollTop = sidebarScrollTop;
|
||
} else {
|
||
// scroll sidebar to current active section when navigating via "next/previous chapter" buttons
|
||
var activeSection = document.querySelector('#sidebar .active');
|
||
if (activeSection) {
|
||
activeSection.scrollIntoView({ block: 'center' });
|
||
}
|
||
}
|
||
</script>
|
||
|
||
<div id="page-wrapper" class="page-wrapper">
|
||
|
||
<div class="page">
|
||
<div id="menu-bar-hover-placeholder"></div>
|
||
<div id="menu-bar" class="menu-bar sticky">
|
||
<div class="left-buttons">
|
||
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
||
<i class="fa fa-bars"></i>
|
||
</label>
|
||
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
||
<i class="fa fa-paint-brush"></i>
|
||
</button>
|
||
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
||
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
||
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
||
</ul>
|
||
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
||
<i class="fa fa-search"></i>
|
||
</button>
|
||
</div>
|
||
|
||
<h1 class="menu-title">Andrew's Blog</h1>
|
||
|
||
<div class="right-buttons">
|
||
<a href="https://gitlink.org.cn/dnrops/dnrops.gitlink.net.git" title="Git repository" aria-label="Git repository">
|
||
<i id="git-repository-button" class="fa fa-github"></i>
|
||
</a>
|
||
|
||
</div>
|
||
</div>
|
||
|
||
<div id="search-wrapper" class="hidden">
|
||
<form id="searchbar-outer" class="searchbar-outer">
|
||
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
||
</form>
|
||
<div id="searchresults-outer" class="searchresults-outer hidden">
|
||
<div id="searchresults-header" class="searchresults-header"></div>
|
||
<ul id="searchresults">
|
||
</ul>
|
||
</div>
|
||
</div>
|
||
|
||
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
||
<script>
|
||
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
||
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
||
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
||
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
||
});
|
||
</script>
|
||
|
||
<div id="content" class="content">
|
||
<main>
|
||
<h1 id="ctf中的rsa及攻击方法笔记"><a class="header" href="#ctf中的rsa及攻击方法笔记">CTF中的RSA及攻击方法笔记</a></h1>
|
||
<h2 id="数论"><a class="header" href="#数论">数论</a></h2>
|
||
<h3 id="模运算规则"><a class="header" href="#模运算规则">模运算规则:</a></h3>
|
||
<p>模运算与基本四则运算有些相似，但是除法例外。其规则如下:
|
||
(a + b) % p = (a % p + b % p) % p
|
||
(a - b) % p = (a % p - b % p) % p
|
||
(a * b) % p = (a % p * b % p) % p
|
||
(a ^ b) % p = ((a % p)^b) % p
|
||
结合律：
|
||
((a+b) % p + c) % p = (a + (b+c) % p) % p
|
||
((a*b) % p * c)% p = (a <em>(b</em>c)%p) % p
|
||
交换律：
|
||
(a + b) % p = (b + a) % p
|
||
(a * b) % p = (b * a) % p
|
||
分配律：
|
||
((a +b)% p * c) % p = ((a * c) %p + (b * c) % p) % p
|
||
重要定理：
|
||
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)
|
||
若a≡b (% p)，则对于任意的正整数c，都有(a * c) ≡ (b * c) (%p)
|
||
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
|
||
(a * c) ≡ (b * d) (%p)</p>
|
||
<h3 id="最大公因子"><a class="header" href="#最大公因子">最大公因子</a></h3>
|
||
<p>两个数互素是指：除了它们除了1外没有共同的因子。如果a和n的最大公因子等于1，那么可写作
|
||
$gcd(a,n)=1$</p>
|
||
<h4 id="欧几里得算法"><a class="header" href="#欧几里得算法">欧几里得算法</a></h4>
|
||
<p>又称碾转相除法，我们通常使用该方法计算最大公因子。</p>
|
||
<h4 id="欧几里得扩展算法"><a class="header" href="#欧几里得扩展算法">欧几里得扩展算法</a></h4>
|
||
<p>如果gcd(a, b) = c，则存在x, y，使得c = ax + by。</p>
|
||
<h3 id="同余"><a class="header" href="#同余">同余</a></h3>
|
||
<p>两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。 记作：a≡b (mod m)， 读作：a同余于b模m，或读作a与b对模m同余，例如26≡2(mod 12)。</p>
|
||
<h4 id="模的逆元"><a class="header" href="#模的逆元">模的逆元</a></h4>
|
||
<p>简单来说，求a的逆，就是找一个 $x$，使得$1 = (a*x){\pmod n}$
|
||
也可记作 $a^{-1} \equiv x{\pmod {n}}$</p>
|
||
<h3 id="费马小定理和欧拉定理"><a class="header" href="#费马小定理和欧拉定理">费马小定理和欧拉定理</a></h3>
|
||
<p><strong>费马小定理</strong>是数论中的一个定理：假如 ${a}$ 是一个整数，${p}$ 是一个质数，那么${a^{p}-a}$是 $p$ 的倍数，可以表示为 $$a^{p}\equiv a{\pmod {p}}$$ 如果a不是p的倍数，这个定理也可以写成 $$a^{{p-1}}\equiv 1{\pmod {p}}$$ <strong>欧拉定理</strong>若$n,a$为正整数，且$n,a$互素（即$gcd(a,n)=1$），那么 $$a^{{\varphi (n)}}\equiv 1{\pmod n}$$
|
||
因为欧拉定理是费马小定理的推广，所以欧拉定理的条件对任意互素的a和n与费马小定理的条件若p是素数，a是正整数且不能被p整除相比不可能是缩小范围。
|
||
可参考：https://www.cnblogs.com/nysanier/archive/2011/04/12/2014000.html</p>
|
||
<h3 id="中国剩余定理"><a class="header" href="#中国剩余定理">中国剩余定理</a></h3>
|
||
<p>可参考：https://blog.csdn.net/u010468553/article/details/38346195/</p>
|
||
<h2 id="rsa原理基础题目"><a class="header" href="#rsa原理基础题目">RSA原理+基础题目</a></h2>
|
||
<p>参考1：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/ 参考2：https://bbs.pediy.com/thread-263069.htm 基于大整数因数分解难题。</p>
|
||
<h1 id="rsa"><a class="header" href="#rsa">RSA</a></h1>
|
||
<h3 id="rsa简介"><a class="header" href="#rsa简介">RSA简介</a></h3>
|
||
<p>倘若在加解密信息的过程中，能让加密密钥（公钥）与解密密钥（私钥）不同，即</p>
|
||
<pre><code>1. 甲要传密信给乙，乙先根据某种算法得出本次与甲通信的公钥与私钥；
|
||
2. 乙将公钥传给甲（公钥可以让任何人知道，即使泄露也没有任何关系）；
|
||
3. 甲使用乙传给的公钥加密要发送的信息原文m，发送给乙密文c；
|
||
4. 乙使用自己的私钥解密密文c，得到信息原文m .
|
||
</code></pre>
|
||
<h3 id="数学概念"><a class="header" href="#数学概念">数学概念</a></h3>
|
||
<p>需要了解的几个数学概念
|
||
1.质数与互质数
|
||
2.欧拉函数
|
||
3.欧拉定理
|
||
4.模反元素
|
||
5.同余</p>
|
||
<h3 id="质数与互质数"><a class="header" href="#质数与互质数">质数与互质数</a></h3>
|
||
<p>一个大于1的自然数，除了1和它本身外，不能被其他自然数整除（除0以外）的数称之为质数（素数）；否则称为合数。
|
||
公约数只有1的两个数，叫做互质数。
|
||
1.任意两个质数一定构成互质数（如3与11、53与61）；
|
||
2.大数是质数的两个数一定是互质数（如97与88）；
|
||
在RSA算法中，我们通常使用以上第1条与第2条，即选取两个本身都是质数的数作为互质数</p>
|
||
<h3 id="欧拉函数"><a class="header" href="#欧拉函数">欧拉函数</a></h3>
|
||
<p>任意给定正整数n，计算在小于等于n的正整数之中，有多少个与n构成互质关系？
|
||
计算这个值的方法就叫做欧拉函数，以φ(n)表示.
|
||
例如，在1到8之中，与8形成互质关系的是1、3、5、7，所以φ(n)=4
|
||
在RSA算法中，我们需要明白欧拉函数对以下定理成立
|
||
1.如果n可以分解成两个互质的整数之积，即n=p×q，则有：φ(n)=φ(pq)=φ(p)φ(q);
|
||
2.根据“大数是质数的两个数一定是互质数”可以知道：
|
||
一个数如果是质数，则小于它的所有正整数与它都是互质数；
|
||
所以如果一个数p是质数，则有：φ(p)=p-1
|
||
由上易得，若我们知道一个数n可以分解为两个质数p和q的乘积，则有
|
||
φ(n)=(p-1)(q-1)</p>
|
||
<h3 id="欧拉定理"><a class="header" href="#欧拉定理">欧拉定理</a></h3>
|
||
<p>如果两个正整数a和n互质，则n的欧拉函数φ(n)可以让下面的等式成立：
|
||
aφ(n)≡1(modn)</p>
|
||
<h3 id="模运算与模反元素"><a class="header" href="#模运算与模反元素">模运算与模反元素</a></h3>
|
||
<p>模运算：让m去被n整除，只取所得的余数作为结果，就叫做模运算。
|
||
例如，10 mod 3 = 1 、26 mod 6 = 2 、28 mod 2 = 0
|
||
模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1
|
||
ab≡1( mod n)
|
||
这时候，b就是a的模反元素</p>
|
||
<h3 id="同余-1"><a class="header" href="#同余-1">同余</a></h3>
|
||
<p>“≡”是数论中表示同余的符号，定义如下：
|
||
给定一个正整数m，如果两个整数a和b满足a-b能被m整除，即(a-b) mod m=0，
|
||
那么就称整数a与b对模m同余，记作a≡b(modm)，同时可成立a mod m=b</p>
|
||
<h3 id="需要记住的参数"><a class="header" href="#需要记住的参数">需要记住的参数</a></h3>
|
||
<p>p,q:大整数N的两个因子（factor）
|
||
N:大整数N，我们称之为模数（modulus）
|
||
e,d:互为模反数的两个指数（exponent）
|
||
c,m:密文和明文，这里一般指的是一个十进制的数
|
||
e：公钥
|
||
d：私钥</p>
|
||
<h3 id="rsa加密流程"><a class="header" href="#rsa加密流程">RSA加密流程</a></h3>
|
||
<ul>
|
||
<li>首先选择两个互为质数p和q (q与p互素，公因数只有1)</li>
|
||
<li>求出n = p * q</li>
|
||
<li>φ(n) = (p−1)*(q−1) 欧拉公式</li>
|
||
<li>公钥 e : 随机取，要求：e 和 φ(n) 互素（公因数只有 1）; 1< e < φ(n)；</li>
|
||
<li>私钥 d ：ed ≡ 1 （mod φ(n) ） （ed 除以 φ(n) 的 余数 为 1 ）</li>
|
||
<li>e与d互为模反元素。</li>
|
||
<li>明文加密后的密文c = pow(m, e, n)
|
||
<img src="../../img_list/rsa1.png" alt="image" /></li>
|
||
<li>密文解密后的明文m = pow(c, d, n)
|
||
<img src="../../img_list/rsa2.png" alt="image" /></li>
|
||
</ul>
|
||
<pre><code>pow(x, y[, z])
|
||
函数是计算x的y次方，如果z在存在，则再对结果进行取模，其结果等效于pow(x,y) %z
|
||
</code></pre>
|
||
<h3 id="依赖库的安装"><a class="header" href="#依赖库的安装">依赖库的安装</a></h3>
|
||
<pre><code class="language-bash">apt-get install libgmp-dev
|
||
apt-get install libmpfr-dev
|
||
apt-get install libmpc-dev
|
||
apt-get install python3-pip
|
||
pip install gmpy2
|
||
</code></pre>
|
||
<h3 id="rsa题目"><a class="header" href="#rsa题目">RSA题目</a></h3>
|
||
<h4 id="简单"><a class="header" href="#简单">简单</a></h4>
|
||
<p>在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
|
||
求解出d作为flag提交</p>
|
||
<pre><code class="language-python">import gmpy2
|
||
p=473398607161
|
||
q=4511491
|
||
e=17
|
||
d=gmpy2.invert(e,(q-1)*(p-1)) # 求逆元，de ≡ 1 mod n
|
||
print(d)
|
||
</code></pre>
|
||
<h4 id="进阶"><a class="header" href="#进阶">进阶</a></h4>
|
||
<h2 id="rsarsa"><a class="header" href="#rsarsa">rsarsa</a></h2>
|
||
<p>Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
|
||
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
|
||
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
|
||
e = 65537
|
||
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
|
||
Use RSA to find the secret message</p>
|
||
<pre><code class="language-python"># 已知 p q e c 求 m
|
||
import gmpy2
|
||
p =9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
|
||
q =11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
|
||
e = 65537
|
||
n = p*q
|
||
c =83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
|
||
d = gmpy2.invert(e,(p-1)*(q-1)) # d是私钥
|
||
m = gmpy2.powmod(c,d,n) # 幂取模，结果是 C = (M^e) mod n
|
||
# m = pow(c,d,n)
|
||
print(m)
|
||
</code></pre>
|
||
<h3 id="buuctf-rsa"><a class="header" href="#buuctf-rsa">BUUCTF-RSA</a></h3>
|
||
<p>题目描述：
|
||
在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17，求解出d作为flag提交
|
||
解题：</p>
|
||
<pre><code>import gmpy2
|
||
p,q,e = 473398607161, 4511491, 17
|
||
phi = (p-1) * (q-1)
|
||
d = gmpy2.invert(e, phi)
|
||
print(d)
|
||
</code></pre>
|
||
<h3 id="buuctf-rsarsa"><a class="header" href="#buuctf-rsarsa">BUUCTF-rsarsa</a></h3>
|
||
<p>题目描述：
|
||
Math is cool! Use the RSA algorithm to decode the secret message, c, p, q, and e are parameters for the RSA algorithm.
|
||
p = 9648423029010515676590551740010426534945737639235739800643989352039852507298491399561035009163427050370107570733633350911691280297777160200625281665378483
|
||
q = 11874843837980297032092405848653656852760910154543380907650040190704283358909208578251063047732443992230647903887510065547947313543299303261986053486569407
|
||
e = 65537
|
||
c = 83208298995174604174773590298203639360540024871256126892889661345742403314929861939100492666605647316646576486526217457006376842280869728581726746401583705899941768214138742259689334840735633553053887641847651173776251820293087212885670180367406807406765923638973161375817392737747832762751690104423869019034
|
||
Use RSA to find the secret message</p>
|
||
<h2 id="rsa数论"><a class="header" href="#rsa数论">RSA+数论</a></h2>
|
||
<h3 id="2018-codegate-ctf-rsababy"><a class="header" href="#2018-codegate-ctf-rsababy">2018 CodeGate CTF Rsababy</a></h3>
|
||
<p>题目描述：
|
||
e = 65537
|
||
n = p * q
|
||
pi_n = (p-1)<em>(q-1)
|
||
d = mulinv(e, pi_n)
|
||
h = (d+p)^(d-p)
|
||
g = d</em>(p-0xdeadbeef)
|
||
解析参看：
|
||
https://github.com/ashutosh1206/Crypto-CTF-Writeups/tree/master/2018/Codegate-CTF-Preliminary/RSAbaby
|
||
解题：</p>
|
||
<pre><code>from Crypto.Util.number import *
|
||
# g,N,Encrypted_Data已知
|
||
e = 65537
|
||
# Using Euler's Theorem and Fermat's Little Theorem we have
|
||
t1 = pow(2, e*g, N)
|
||
t2 = pow(2, 0xdeadbeef, N)
|
||
p = GCD((t1*t2)-2,N)
|
||
assert N % p == 0
|
||
q = N / p
|
||
phin = (p-1)*(q-1)
|
||
d = inverse(e, phin)
|
||
m = pow(Encrypted_Data, d, N)
|
||
print long_to_bytes(m)
|
||
</code></pre>
|
||
<h2 id="模相关攻击"><a class="header" href="#模相关攻击">模相关攻击</a></h2>
|
||
<h3 id="暴力分解n"><a class="header" href="#暴力分解n">暴力分解N</a></h3>
|
||
<h4 id="可攻击特征"><a class="header" href="#可攻击特征">可攻击特征</a></h4>
|
||
<p>在 N 的比特位数小于 512 的时候，可以采用大整数分解的策略获取 p 和 q。</p>
|
||
<h4 id="攻击方法"><a class="header" href="#攻击方法">攻击方法</a></h4>
|
||
<p>大整数分解一般有以下两种方法：</p>
|
||
<ol>
|
||
<li>在线数据库查询：<a href="http://factordb.com/">http://factordb.com/</a></li>
|
||
<li>yafu工具</li>
|
||
</ol>
|
||
<h4 id="jarvisoj---easy-rsa"><a class="header" href="#jarvisoj---easy-rsa">JarvisOJ - Easy RSA</a></h4>
|
||
<p>题目描述：
|
||
还记得 veryeasy RSA 吗？是不是不难？那继续来看看这题吧，这题也不难。
|
||
已知一段 RSA 加密的信息为：0xdc2eeeb2782c 且已知加密所用的公钥：
|
||
N=322831561921859 e = 23
|
||
请解密出明文，提交时请将数字转化为 ascii 码提交
|
||
比如你解出的明文是 0x6162，那么请提交字符串 ab
|
||
提交格式：PCTF{明文字符串}
|
||
解题：</p>
|
||
<h1 id="经过-httpfactordbcom-查询得出1357488123781539"><a class="header" href="#经过-httpfactordbcom-查询得出1357488123781539">经过 http://factordb.com/ 查询得出：13574881,23781539</a></h1>
|
||
<pre><code>from Crypto.Util.number import long_to_bytes
|
||
import gmpy2
|
||
p,q = 13574881,23781539
|
||
n = q*p
|
||
e = 23
|
||
c = 0xdc2eeeb2782c
|
||
phi = (q-1) * (p-1)
|
||
d = gmpy2.invert(e,phi)
|
||
m = gmpy2.powmod(c,d,n)
|
||
m = long_to_bytes(m)
|
||
print(m)
|
||
</code></pre>
|
||
<h3 id="多因子"><a class="header" href="#多因子">多因子</a></h3>
|
||
<h4 id="可攻击特征-1"><a class="header" href="#可攻击特征-1">可攻击特征</a></h4>
|
||
<p>N可被分解为多个素数</p>
|
||
<h4 id="原理"><a class="header" href="#原理">原理</a></h4>
|
||
<p>如果选取两个以上的素数，记为 $p1,p2,p3…$，它们相乘得到 nn，那么：
|
||
$φ(n)=(p1−1)(p2−1)(p3−1)$
|
||
公钥、私钥、加解密都与一般 RSA 相同。
|
||
选取多因子，虽然会减少生成密钥的时间，但同样也更容易被破解。</p>
|
||
<h4 id="2018-picoctfsuper-safe-rsa-3"><a class="header" href="#2018-picoctfsuper-safe-rsa-3">2018 picoctf：Super Safe RSA 3</a></h4>
|
||
<p><strong>题目</strong>
|
||
每次<code>nc</code>连接可以获得不同的 cc、nn、ee。
|
||
例如一次连接中：
|
||
c: 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
|
||
n: 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
|
||
e: 65537
|
||
<strong>解题</strong>
|
||
首先用<code>yafu</code>经过多次分解直到所有因子都为素数，可以得到 32 个素数因子，然后直接求解即可：</p>
|
||
<pre><code>from Crypto.Util.number import *
|
||
import gmpy2
|
||
c = 236434294562852381842307785543347919217676481857496426677823656807506421759144963030501769311835411762026907848397529006599563288690089282702818198177368099766733506715831007535690273535741585530721389732916130816863687011754081219886436105201386044253051204304648556642980507914261370486658516914518976
|
||
n = 607623369882890591735782141073772197087735470451907161056918749085797298608061697204877318116530061370098150393008398852309935398612508655661345572182951783541048774456584255774063319762705994011630127672153887410829669163686086432067585460780467260542209687551454132414709631582428726568293866157915237
|
||
e = 65537
|
||
factors = [2209835647, 3279221983, 2203115203, 3083863231, 2624125561, 4051923611, 3870883097, 3919135769, 3746033843, 2349626557, 2911452569, 2280078727, 3772965367, 2486744167, 3816147749, 2613884417, 2657517431, 2808514571, 3516405091, 3393739981, 2965911017, 2282964227, 2794765357, 2162896789, 4177000211, 2804308609, 2549752151, 2206071653, 2336473199, 2647948099, 3656705023, 2574736709]
|
||
phi = 1
|
||
for x in factors:
|
||
phi *= (x-1)
|
||
d = gmpy2.invert(e, phi)
|
||
print long_to_bytes(pow(c, d, n))
|
||
</code></pre>
|
||
<h3 id="p或q选取不当分解n"><a class="header" href="#p或q选取不当分解n">p或q选取不当分解N</a></h3>
|
||
<p>当 RSA 中 p 和 q 选取不当时，我们也可以进行攻击。比如一般有以下四种情况</p>
|
||
<h4 id="p-q-很大"><a class="header" href="#p-q-很大">$|p-q|$ 很大</a></h4>
|
||
<p>当$|p-q|$ 很大时，那么其中p或q有一个值一定很小，我们可以用试除法穷举p或q。</p>
|
||
<h4 id="p-q-较小"><a class="header" href="#p-q-较小">$|p-q|$ 较小</a></h4>
|
||
<p>参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_module_attack-zh/#p-q_1
|
||
<strong>例题：[GWCTF 2019]BabyRSA</strong>
|
||
[GWCTF 2019]BabyRSA
|
||
题目描述：</p>
|
||
<pre><code>import hashlib
|
||
import sympy
|
||
from Crypto.Util.number import *
|
||
flag = 'GWHT{******}'
|
||
secret = '******'
|
||
assert(len(flag) == 38)
|
||
half = len(flag) / 2
|
||
flag1 = flag[:half]
|
||
flag2 = flag[half:]
|
||
secret_num = getPrime(1024) * bytes_to_long(secret)
|
||
p = sympy.nextprime(secret_num)
|
||
q = sympy.nextprime(p)
|
||
N = p * q
|
||
e = 0x10001
|
||
F1 = bytes_to_long(flag1)
|
||
F2 = bytes_to_long(flag2)
|
||
c1 = F1 + F2
|
||
c2 = pow(F1, 3) + pow(F2, 3)
|
||
assert(c2 < N)
|
||
m1 = pow(c1, e, N)
|
||
m2 = pow(c2, e, N)
|
||
output = open('secret', 'w')
|
||
output.write('N=' + str(N) + '\n')
|
||
output.write('m1=' + str(m1) + '\n')
|
||
output.write('m2=' + str(m2) + '\n')
|
||
output.close()
|
||
</code></pre>
|
||
<p>题目解析：
|
||
因为p和q相差较小，一般来说相差千万都是比较小的，可以有两种解法</p>
|
||
<ol>
|
||
<li>我们对N开根号，然后从$\sqrt N$ 到$N$依此遍历</li>
|
||
<li>yafu分解
|
||
解题：</li>
|
||
</ol>
|
||
<pre><code>import gmpy2
|
||
from Crypto.Util.number import isPrime, long_to_bytes
|
||
from z3 import *
|
||
N = 636585149594574746909030160182690866222909256464847291783000651837227921337237899651287943597773270944384034858925295744880727101606841413640006527614873110651410155893776548737823152943797884729130149758279127430044739254000426610922834573094957082589539445610828279428814524313491262061930512829074466232633130599104490893572093943832740301809630847541592548921200288222432789208650949937638303429456468889100192613859073752923812454212239908948930178355331390933536771065791817643978763045030833712326162883810638120029378337092938662174119747687899484603628344079493556601422498405360731958162719296160584042671057160241284852522913676264596201906163
|
||
e = 65537
|
||
m1 = 90009974341452243216986938028371257528604943208941176518717463554774967878152694586469377765296113165659498726012712288670458884373971419842750929287658640266219686646956929872115782173093979742958745121671928568709468526098715927189829600497283118051641107305128852697032053368115181216069626606165503465125725204875578701237789292966211824002761481815276666236869005129138862782476859103086726091860497614883282949955023222414333243193268564781621699870412557822404381213804026685831221430728290755597819259339616650158674713248841654338515199405532003173732520457813901170264713085107077001478083341339002069870585378257051150217511755761491021553239
|
||
m2 = 487443985757405173426628188375657117604235507936967522993257972108872283698305238454465723214226871414276788912058186197039821242912736742824080627680971802511206914394672159240206910735850651999316100014691067295708138639363203596244693995562780286637116394738250774129759021080197323724805414668042318806010652814405078769738548913675466181551005527065309515364950610137206393257148357659666687091662749848560225453826362271704292692847596339533229088038820532086109421158575841077601268713175097874083536249006018948789413238783922845633494023608865256071962856581229890043896939025613600564283391329331452199062858930374565991634191495137939574539546
|
||
sqrt_N = gmpy2.iroot(N, 2)[0]
|
||
for i in range(sqrt_N, N):
|
||
if isPrime(i):
|
||
if N % i == 0:
|
||
p = i
|
||
q = N // i
|
||
break
|
||
phi = (p - 1) * (q - 1)
|
||
d = gmpy2.invert(e, phi)
|
||
c1 = gmpy2.powmod(m1, d, N)
|
||
c2 = gmpy2.powmod(m2, d, N)
|
||
# 当前半部分计算出a和b后，使用z3分解
|
||
s = Solver()
|
||
F1, F2 = Ints('F1 F2')
|
||
s.add(F1 + F2 == 2732509502629189160482346120094198557857912754)
|
||
s.add(F1 ** 3 + F2 ** 3 == 5514544075236012543362261483183657422998274674127032311399076783844902086865451355210243586349132992563718009577051164928513093068525554)
|
||
if s.check() == sat:
|
||
F1 = (s.model()[F1]).as_long()
|
||
F2 = (s.model()[F2]).as_long()
|
||
flag1 = long_to_bytes(F1)
|
||
flag2 = long_to_bytes(F2)
|
||
flag = flag1 + flag2
|
||
print(flag)
|
||
</code></pre>
|
||
<h4 id="p-1光滑或p1光滑"><a class="header" href="#p-1光滑或p1光滑">$p-1$光滑或$p+1$光滑</a></h4>
|
||
<p>光滑数（Smooth Number）指可以分解为小素数乘积的正整数。
|
||
当 p 是 N 的因数，并且 $p−1$ 是光滑数，可能可以使用 Pollard’s p − 1 算法来分解 N。</p>
|
||
<h5 id="原理-1"><a class="header" href="#原理-1">原理</a></h5>
|
||
<p>根据费马小定理：
|
||
如果p是一个素数，而整数a不是p的倍数，则有 $a^{p-1} \equiv 1 \bmod p$
|
||
则：$a^{t(p-1)} \equiv 1^t \equiv 1 \bmod p$
|
||
可改为等式：$a^{t(p-1)} - 1 = k * p$
|
||
即$a^{t(p-1)} - 1$是p的倍数。
|
||
然后根据 Pollard’s p - 1 算法：
|
||
如果 p−1 是一些很小质数的乘积，那么 n! 就能被 p−1 整除。即 n!=t(p−1)。
|
||
对于每一个 n=2,3,4,…，任意选择一个底数 a（事实上，可以简单地选择为 2），并计算：
|
||
$gcd(a^{n!} - 1, N)$
|
||
如果结果不为 1 或 NNN，那么就已成功分解 NNN。
|
||
但n较大时，直接计算n!将会很消耗资源。在便利n时，可以简化运算。
|
||
因为：$a^{n!} \bmod N = (a \bmod N) ^ {n!} \bmod N$
|
||
所以：$a^{n!} \bmod N = \begin{cases} (a \bmod N) ^ 2 \bmod N & \text{n = 2} \ (a^{(n-1)!} \bmod N) ^ n \bmod N & \text{n >= 3} \end{cases} $</p>
|
||
<h5 id="解题脚本"><a class="header" href="#解题脚本">解题脚本</a></h5>
|
||
<pre><code>import gmpy2
|
||
def Pollards_p_1(N):
|
||
a = 2
|
||
n = 2
|
||
while True:
|
||
a = pow(a, n, N)
|
||
res = gmpy2.gcd(a-1, N)
|
||
if res != 1 and res != N:
|
||
print 'n =', n
|
||
print 'p =', res
|
||
return res
|
||
n += 1
|
||
</code></pre>
|
||
<h5 id="nctf2019-childrsa"><a class="header" href="#nctf2019-childrsa">[NCTF2019] childRSA</a></h5>
|
||
<p><strong>题目</strong></p>
|
||
<pre><code>from random import choice
|
||
from Crypto.Util.number import isPrime, sieve_base as primes
|
||
from flag import flag
|
||
def getPrime(bits):
|
||
while True:
|
||
n = 2
|
||
while n.bit_length() < bits:
|
||
n *= choice(primes)
|
||
if isPrime(n + 1):
|
||
return n + 1
|
||
e = 0x10001
|
||
m = int.from_bytes(flag.encode(), 'big')
|
||
p, q = [getPrime(2048) for _ in range(2)]
|
||
n = p * q
|
||
c = pow(m, e, n)
|
||
# n = 3284971819733758182300224371705765921850251900438699666088510059287220194883415554312592439561492896275057966734...388249513
|
||
# c = 2630801835673985389538224010996889417516673128370292700216526899877370833521633899705831415771714713108329655131...605279108
|
||
</code></pre>
|
||
<p><strong>解题</strong>
|
||
可以发现 p 和 q 是由前10000个随机的许多小质数乘积加1得到，即p−1为许多小质数的乘积。那么可以利用Pollard’s p − 1 算法来分解 N。</p>
|
||
<pre><code>e = 0x10001
|
||
n = 32849718197337581823002243717057659218502519004386996660885100592872201948834155543125924395614928962750579667346279456710633774501407292473006312537723894221717638059058796679686953564471994009285384798450493756900459225040360430847240975678450171551048783818642467506711424027848778367427338647282428667393241157151675410661015044633282064056800913282016363415202171926089293431012379261585078566301060173689328363696699811123592090204578098276704877408688525618732848817623879899628629300385790344366046641825507767709276622692835393219811283244303899850483748651722336996164724553364097066493953127153066970594638491950199605713033004684970381605908909693802373826516622872100822213645899846325022476318425889580091613323747640467299866189070780620292627043349618839126919699862580579994887507733838561768581933029077488033326056066378869170169389819542928899483936705521710423905128732013121538495096959944889076705471928490092476616709838980562233255542325528398956185421193665359897664110835645928646616337700617883946369110702443135980068553511927115723157704586595844927607636003501038871748639417378062348085980873502535098755568810971926925447913858894180171498580131088992227637341857123607600275137768132347158657063692388249513
|
||
c = 26308018356739853895382240109968894175166731283702927002165268998773708335216338997058314157717147131083296551313334042509806229853341488461087009955203854253313827608275460592785607739091992591431080342664081962030557042784864074533380701014585315663218783130162376176094773010478159362434331787279303302718098735574605469803801873109982473258207444342330633191849040553550708886593340770753064322410889048135425025715982196600650740987076486540674090923181664281515197679745907830107684777248532278645343716263686014941081417914622724906314960249945105011301731247324601620886782967217339340393853616450077105125391982689986178342417223392217085276465471102737594719932347242482670320801063191869471318313514407997326350065187904154229557706351355052446027159972546737213451422978211055778164578782156428466626894026103053360431281644645515155471301826844754338802352846095293421718249819728205538534652212984831283642472071669494851823123552827380737798609829706225744376667082534026874483482483127491533474306552210039386256062116345785870668331513725792053302188276682550672663353937781055621860101624242216671635824311412793495965628876036344731733142759495348248970313655381407241457118743532311394697763283681852908564387282605279108
|
||
p = pollards_p_1(n)
|
||
q = n // p
|
||
assert p*q == n
|
||
d = gmpy2.invert(e, (p-1)*(q-1))
|
||
m = pow(c, d, n)
|
||
print(long_to_bytes(m))
|
||
</code></pre>
|
||
<h3 id="模不互素"><a class="header" href="#模不互素">模不互素</a></h3>
|
||
<h4 id="可攻击特征-2"><a class="header" href="#可攻击特征-2">可攻击特征</a></h4>
|
||
<p>当存在两个公钥的 N 不互素时</p>
|
||
<h4 id="原理-2"><a class="header" href="#原理-2">原理</a></h4>
|
||
<p>当存在两个公钥的 N 不互素时，我们显然可以直接对这两个数求最大公因数，然后直接获得 p，q，进而获得相应的私钥。具体来说：
|
||
当$n1 = p1 * q1$，$n2 = p1 * q2$ 时，我们先求出p1，然后再求出对应的q1和q2即可。</p>
|
||
<h4 id="sctf-rsa2"><a class="header" href="#sctf-rsa2">SCTF-RSA2</a></h4>
|
||
<p>题目链接：https://github.com/ohroot/rsatools/blob/master/demos/sctf/rsa2/syc_security_system_traffic2.pcap
|
||
题目描述：题目是一个流量包，我们从中提取出两个
|
||
<strong>解题</strong></p>
|
||
<pre><code>import gmpy2
|
||
from Crypto.Util.number import long_to_bytes
|
||
n1 = 20823369114556260762913588844471869725762985812215987993867783630051420241057912385055482788016327978468318067078233844052599750813155644341123314882762057524098732961382833215291266591824632392867716174967906544356144072051132659339140155889569810885013851467056048003672165059640408394953573072431523556848077958005971533618912219793914524077919058591586451716113637770245067687598931071827344740936982776112986104051191922613616045102859044234789636058568396611030966639561922036712001911238552391625658741659644888069244729729297927279384318252191421446283531524990762609975988147922688946591302181753813360518031
|
||
n2 = 19083821613736429958432024980074405375408953269276839696319265596855426189256865650651460460079819368923576109723079906759410116999053050999183058013281152153221170931725172009360565530214701693693990313074253430870625982998637645030077199119183041314493288940590060575521928665131467548955951797198132001987298869492894105525970519287000775477095816742582753228905458466705932162641076343490086247969277673809512472546919489077884464190676638450684714880196854445469562733561723325588433285405495368807600668761929378526978417102735864613562148766250350460118131749533517869691858933617013731291337496943174343464943
|
||
p1 = gmpy2.gcd(n1, n2)
|
||
q1 = n1 // p1
|
||
e = 65537
|
||
phi = (p1 - 1) * (q1 - 1)
|
||
d = gmpy2.invert(e, phi)
|
||
cipher = 0x68d5702b70d18238f9d4a3ac355b2a8934328250efd4efda39a4d750d80818e6fe228ba3af471b27cc529a4b0bef70a2598b80dd251b15952e6a6849d366633ed7bb716ed63c6febd4cd0621b0c四ebfe5235de03d4ee016448de1afbbe61144845b580eed8be8127a8d92b37f9ef670b3cdd5af613c76f58ca1a9f6f03f1bc11addba30b61bb191efe0015e971b8f78375faa257a60b355050f6435d94b49eab07075f40cb20bb8723d02f5998d5538e8dafc80cc58643c91f6c0868a7a7bf3bf6a9b4b6e79e0a80e89d430f0c049e1db4883c50db066a709b89d74038c34764aac286c36907b392bc299ab8288f9d7e372868954a92cdbf634678f7294096c7
|
||
plain = gmpy2.powmod(cipher, d, n1)
|
||
print(long_to_bytes(plain))
|
||
</code></pre>
|
||
<h3 id="共模攻击"><a class="header" href="#共模攻击">共模攻击</a></h3>
|
||
<h4 id="可攻击特征-3"><a class="header" href="#可攻击特征-3">可攻击特征</a></h4>
|
||
<p>当两个用户使用相同的模数 N、不同的私钥时，加密同一明文消息时即存在共模攻击。
|
||
具体说就是：明文m、模数n相同，公钥指数e、密文c不同，gcd(e1,e2)==1也就是e1和e2互质时候，可能导致共模攻击。</p>
|
||
<h4 id="原理-3"><a class="header" href="#原理-3">原理</a></h4>
|
||
<p>设两个用户的公钥分别为 $e_1$ 和 $e_2$，且两者互质。明文消息为 $m$，密文分别为：
|
||
$$ c_1 = m^{e_1}\bmod N $$
|
||
$$ c_2 = m^{e_2}\bmod N $$
|
||
当攻击者截获 $c_1$ 和 $c_2$ 后，就可以恢复出明文。用扩展欧几里得算法求出 $re_1+se_2=1\bmod n$ 的两个整数 $r$ 和 $s$，由此可得：
|
||
$$ c{1}^{r}c{2}^{s} \equiv m^{re_1}m^{se_2}\bmod n\ $$
|
||
$$ c{1}^{r}c{2}^{s}\equiv m^{(re_1+se_2)} \bmod n\ $$
|
||
$$c{1}^{r}c{2}^{s}\equiv m\bmod n $$</p>
|
||
<h4 id="jarvisoj-very-hard-rsa"><a class="header" href="#jarvisoj-very-hard-rsa">jarvisoj-very hard RSA</a></h4>
|
||
<p><strong>题目描述</strong>
|
||
前几题因为N太小，都被你攻破了，出题人这次来了个RSA4096，是否接受挑战就看你了。</p>
|
||
<pre><code>#!/usr/bin/env python
|
||
import random
|
||
N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L
|
||
def pad_even(x):
|
||
return ('', '0')[len(x)%2] + x
|
||
e1 = 17
|
||
e2 = 65537
|
||
fi = open('flag.txt','rb')
|
||
fo1 = open('flag.enc1','wb')
|
||
fo2 = open('flag.enc2','wb')
|
||
data = fi.read()
|
||
fi.close()
|
||
while (len(data)<512-11):
|
||
data = chr(random.randint(0,255))+data
|
||
data_num = int(data.encode('hex'),16)
|
||
encrypt1 = pow(data_num,e1,N)
|
||
encrypt2 = pow(data_num,e2,N)
|
||
fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
|
||
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))
|
||
fo1.close()
|
||
fo2.close()
|
||
</code></pre>
|
||
<p><strong>题目分析</strong>
|
||
题目中4096位的RSA加密，硬解肯定是解不开的。我们观察题目特点，题目给出了2个flag.enc文件和一个easyRSA.py的脚本。分析该脚本
|
||
<strong>解题</strong></p>
|
||
<pre><code>import gmpy2
|
||
from Crypto.Util.number import long_to_bytes,bytes_to_long
|
||
e1 = 17
|
||
e2 = 65537
|
||
n = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c四78bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929
|
||
with open('./flag.enc1','rb') as enc1:
|
||
c1 = bytes_to_long(enc1.read())
|
||
with open('./flag.enc2','rb') as enc2:
|
||
c2 = bytes_to_long(enc2.read())
|
||
_, r, s = gmpy2.gcdext(e1, e2)
|
||
m = gmpy2.powmod(c1, r, n) * gmpy2.powmod(c2, s, n) % n
|
||
print(long_to_bytes(m))
|
||
</code></pre>
|
||
<h2 id="公钥指数e的相关攻击"><a class="header" href="#公钥指数e的相关攻击">公钥指数e的相关攻击</a></h2>
|
||
<h3 id="小公钥指数攻击"><a class="header" href="#小公钥指数攻击">小公钥指数攻击</a></h3>
|
||
<h4 id="可攻击特征-4"><a class="header" href="#可攻击特征-4">可攻击特征</a></h4>
|
||
<p>e 特别小，比如 e 为 3。</p>
|
||
<h4 id="原理-4"><a class="header" href="#原理-4">原理</a></h4>
|
||
<p>假设用户使用的密钥 $e=3$，考虑到加密关系满足：
|
||
$c\equiv m^3 \bmod N$
|
||
则：
|
||
$$\begin{align} m^3 &= c+k\times N\ m &= \sqrt[3]{c+k\times n} \end{align}$$</p>
|
||
<h4 id="jarvisoj-extremely-hard-rsa"><a class="header" href="#jarvisoj-extremely-hard-rsa">jarvisoj-Extremely hard RSA</a></h4>
|
||
<p><strong>题目描述</strong>
|
||
没想到RSA4096都被你给破了，一定是我的问题，给了你太多信息，这次我只给你一个flag的加密值和公钥，仍然是RSA4096，我就不信你还能解出来。
|
||
题目附件是两个文件：<code>pubkey.pem</code>、<code>flag.enc</code>
|
||
<strong>解题</strong>
|
||
首先我们使用openssl工具查看公钥文件的一些参数（为了节省篇幅，省略一些解题无关的内容）
|
||
➜ [Jarvis OJ]extremelyhardRSA openssl rsa -pubin -in pubkey.pem -text -modulus
|
||
Public-Key: (4096 bit)
|
||
Modulus:
|
||
00:b0:be:e5:e3:e9:e5:a7:e8:d0:0b:49:33:55:c6:
|
||
…
|
||
Exponent: 3 (0x3)
|
||
Modulus=B0BEE5E3E9E5A7E8D00B493355C618FC8C7D7D03B82E409951C182F398DEE3104580E7BA70D383AE5311475656E8A964D380CB157F48C951ADFA65DB0B122CA40E42FA709189B719A4F0D746E2F6069BAF11CEBD650F14B93C977352FD13B1EEA6D6E1DA775502ABFF89D3A8B3615FD0DB49B88A976BC20568489284E181F6F11E270891C8EF80017BAD238E363039A458470F1749101BC29949D3A4F4038D463938851579C7525A69984F15B5667F34209B70EB261136947FA123E549DFFF00601883AFD936FE411E006E4E93D1A00B0FEA541BBFC8C5186CB6220503A94B2413110D640C77EA54BA3220FC8F4CC6CE77151E29B3E06578C四78BD1BEBE04589EF9A197F6F806DB8B3ECD826CAD24F5324CCDEC6E8FEAD2C2150068602C8DCDC59402CCAC9424B790048CCDD9327068095EFA010B7F196C74BA8C37B128F9E1411751633F78B7B9E56F71F77A1B4DAAD3FC54B5E7EF935D9A72FB176759765522B4BBC02E314D5C06B64D5054B7B096C601236E6CCF45B5E611C805D335DBAB0C35D226CC208D8CE4736BA39A0354426FAE006C7FE52D5267DCFB9C3884F51FDDFDF4A9794BCFE0E1557113749E6C8EF421DBA263AFF68739CE00ED80FD0022EF92D3488F76DEB62BDEF7BEA6026F22A1D25AA2A92D124414A8021FE0C174B9803E6BB5FAD75E186A946A17280770F1243F4387446CCCEB2222A965CC30B3929
|
||
writing RSA key
|
||
—–BEGIN PUBLIC KEY—–
|
||
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY
|
||
…
|
||
写出脚本</p>
|
||
<pre><code>import gmpy2
|
||
from Crypto.PublicKey import RSA
|
||
from Crypto.Util.number import bytes_to_long,long_to_bytes
|
||
from multiprocessing import Pool
|
||
pool = Pool(4)
|
||
with open('./pubkey.pem', 'r') as f:
|
||
key = RSA.importKey(f.read())
|
||
N = key.n
|
||
e = key.e
|
||
with open('flag.enc', 'rb') as f:
|
||
cipher = bytes_to_long(f.read())
|
||
def calc(j):
|
||
a, b = gmpy2.iroot(cipher + j * N, 3)
|
||
if b == 1:
|
||
m = long_to_bytes(a)
|
||
print(m)
|
||
pool.terminate()
|
||
exit()
|
||
def main():
|
||
inputs = range(0, 150000000)
|
||
pool.map(calc, inputs)
|
||
pool.close()
|
||
pool.join()
|
||
if __name__ == '__main__':
|
||
print('start')
|
||
main()
|
||
</code></pre>
|
||
<h3 id="小公钥指数攻击之rabin-算法"><a class="header" href="#小公钥指数攻击之rabin-算法">小公钥指数攻击之Rabin 算法</a></h3>
|
||
<h4 id="可攻击特征-5"><a class="header" href="#可攻击特征-5">可攻击特征</a></h4>
|
||
<p>Rabin 算法的特征在于 $e=2$。</p>
|
||
<h4 id="原理-5"><a class="header" href="#原理-5">原理</a></h4>
|
||
<p>暂略，数学推导。</p>
|
||
<h4 id="jarvisoj-extremely-hard-rsa-1"><a class="header" href="#jarvisoj-extremely-hard-rsa-1">jarvisoj-Extremely hard RSA</a></h4>
|
||
<pre><code>import gmpy2
|
||
import string
|
||
from Crypto.PublicKey import RSA
|
||
from Crypto.Util.number import bytes_to_long,long_to_bytes
|
||
# 读取公钥参数
|
||
with open('pubkey.pem', 'r') as f:
|
||
key = RSA.importKey(f.read())
|
||
N = key.n
|
||
e = key.e
|
||
with open('flag.enc', 'rb') as f:
|
||
cipher = bytes_to_long(f.read())
|
||
p=275127860351348928173285174381581152299
|
||
q=319576316814478949870590164193048041239
|
||
e = 2
|
||
# 计算yp和yq
|
||
inv_p = gmpy2.invert(p, q)
|
||
inv_q = gmpy2.invert(q, p)
|
||
# 计算mp和mq
|
||
mp = pow(cipher, (p + 1) // 4, p)
|
||
mq = pow(cipher, (q + 1) // 4, q)
|
||
# 计算a,b,c,d
|
||
a = (inv_p * p * mq + inv_q * q * mp) % N
|
||
b = N - int(a)
|
||
c = (inv_p * p * mq - inv_q * q * mp) % N
|
||
d = N - int(c)
|
||
for i in (a, b, c, d):
|
||
print(long_to_bytes(i))
|
||
</code></pre>
|
||
<h3 id="私钥指数d的相关攻击"><a class="header" href="#私钥指数d的相关攻击">私钥指数d的相关攻击</a></h3>
|
||
<h4 id="可攻击特征-6"><a class="header" href="#可攻击特征-6">可攻击特征</a></h4>
|
||
<p>首先当 d 泄露之后，我们自然可以解密所有加密的消息。我们甚至还可以对模数 N 进行分解。</p>
|
||
<h4 id="原理-6"><a class="header" href="#原理-6">原理</a></h4>
|
||
<p>我们知道 $ed \equiv 1 \bmod \varphi(n)$，那么存在一个 $k$ 使得
|
||
$ed-1=k\varphi(n)$
|
||
又 $\forall a\in {Z}_n^<em>$，满足 $a^{ed-1}\equiv1(\bmod n)$ 。令
|
||
$ed-1=2^st$
|
||
其中，$t$ 是一个奇数。然后可以证明对于至少一半的 $a\in {Z}_n^</em>$，存在一个 $i\in[1,s]$，使得
|
||
$a^{2^{i-1}t}\not\equiv\pm1(\bmod n),a^{2^{i}t}\equiv1(\bmod n)$
|
||
成立。如果 $a,i$ 满足上述条件，$gcd(a^{2^{i-1}t}-1,n)$ 是 $n$ 的一个非平凡因子，所以可以对 $n$ 进行暴力分解。
|
||
可参考：https://www.di-mgt.com.au/rsa_factorize_n.html</p>
|
||
<h4 id="攻击脚本"><a class="header" href="#攻击脚本">攻击脚本</a></h4>
|
||
<pre><code>#!/usr/bin/env python3
|
||
import random
|
||
import gmpy2
|
||
def divide_pq(ed, n):
|
||
# ed = e*d
|
||
k = ed - 1
|
||
while True:
|
||
g = random.randint(3, n-2)
|
||
t = k
|
||
while True:
|
||
if t % 2 != 0:
|
||
break
|
||
t = t//2
|
||
x = pow(g, t, n)
|
||
if x > 1 and gmpy2.gcd(x-1, n) > 1:
|
||
p = gmpy2.gcd(x-1, n)
|
||
return (p, n//p)
|
||
</code></pre>
|
||
<h4 id="工具"><a class="header" href="#工具">工具</a></h4>
|
||
<p>也可以使用如下工具可以直接进行计算</p>
|
||
<ul>
|
||
<li>RsaConverter.exe (<a href="https://sourceforge.net/projects/rsaconverter/">https://sourceforge.net/projects/rsaconverter/</a>, for windows )</li>
|
||
<li><a href="https://github.com/ius/rsatool/blob/master/rsatool.py">rsatool.py</a>(分解原理如上)</li>
|
||
</ul>
|
||
<h3 id="wieners-attack"><a class="header" href="#wieners-attack">Wiener’s Attack</a></h3>
|
||
<h4 id="可攻击特征-7"><a class="header" href="#可攻击特征-7">可攻击特征</a></h4>
|
||
<p>在 d 比较小 $d<\frac{1}{3}N^{\frac{1}{4}}$ 时，攻击者可以使用 <strong>Wiener’s Attack</strong>来获得私钥。</p>
|
||
<blockquote>
|
||
<p>flatcc备注：e特别大时候也能解？</p>
|
||
</blockquote>
|
||
<h4 id="攻击原理"><a class="header" href="#攻击原理">攻击原理</a></h4>
|
||
<ul>
|
||
<li>https://sagi.io/2016/04/crypto-classics-wieners-rsa-attack/</li>
|
||
</ul>
|
||
<h4 id="2016-hctf-rsa1"><a class="header" href="#2016-hctf-rsa1">2016 HCTF RSA1</a></h4>
|
||
<p>这道题目也是从CTF-WiKi上边摘录的，题目是2016 年 HCTF 中 RSA 1 - Crypto So Interesting，源码链接在这里：https://github.com/Hcamael/ctf-library/tree/master/RSA1
|
||
<strong>题目描述</strong>
|
||
我们直接入手题目核心部分，先来看下题目给出的已知条件，题目内容如下：</p>
|
||
<pre><code># 节选部分内容，下边是题目给出的n和e
|
||
p=getPrime(2048)
|
||
q=getPrime(2048)
|
||
n = p * q
|
||
e, d = get_ed(p, q)
|
||
print "n: ", hex(n)
|
||
print "e: ", hex(e)
|
||
# 下边是e,d的由来
|
||
def get_ed(p, q):
|
||
k = cal_bit(q*p)
|
||
phi_n = (p-1)*(q-1)
|
||
r = random.randint(10, 99)
|
||
while True:
|
||
u = getPrime(k/4 - r)
|
||
if gcd(u, phi_n) != 1:
|
||
continue
|
||
t = invmod(u, phi_n)
|
||
e = pi_b(t)
|
||
if gcd(e, phi_n) == 1:
|
||
break
|
||
d = invmod(e, phi_n)
|
||
return (e, d)
|
||
</code></pre>
|
||
<p><strong>解题思路</strong>
|
||
所以从<code>get_ed()</code>这个函数，我们得知u的位数小于四分之一的n，那么我们就想到了Wiener’s Attack攻击，使用t和n求出u；但要得先求出t来，我们从题目中得知<code>e = pi_b(t)</code>，那么e是又是已知的，这个问题就解决了。
|
||
<strong>解题脚本</strong>
|
||
在自己的<code>rsa_toolset/RSA-Wiener-Attack/exp.py</code></p>
|
||
<pre><code>def wiener_hack(e, n):
|
||
# firstly git clone https://github.com/pablocelayes/rsa-wiener-attack.git !
|
||
frac = ContinuedFractions.rational_to_contfrac(e, n)
|
||
convergents = ContinuedFractions.convergents_from_contfrac(frac)
|
||
for (k, d) in convergents:
|
||
if k != 0 and (e * d - 1) % k == 0:
|
||
phi = (e * d - 1) // k
|
||
s = n - phi + 1
|
||
discr = s * s - 4 * n
|
||
if (discr >= 0):
|
||
t = Arithmetic.is_perfect_square(discr)
|
||
if t != -1 and (s + t) % 2 == 0:
|
||
print("Hacked!")
|
||
return d
|
||
return False
|
||
</code></pre>
|
||
<h2 id="coppersmith-相关攻击"><a class="header" href="#coppersmith-相关攻击">Coppersmith 相关攻击</a></h2>
|
||
<p>相关数学理论基础可参考：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_coppersmith_attack-zh/
|
||
<strong>Coppersmith method</strong>可参考：https://github.com/mimoo/RSA-and-LLL-attacks</p>
|
||
<h3 id="basic-broadcast-attack"><a class="header" href="#basic-broadcast-attack">Basic Broadcast Attack</a></h3>
|
||
<p>中文有人翻译作广播攻击</p>
|
||
<h4 id="可攻击特征-8"><a class="header" href="#可攻击特征-8">可攻击特征</a></h4>
|
||
<p>如果一个用户使用同一个加密指数 e 加密了同一个密文，并发送给了其他 e 个用户。那么就会产生广播攻击。这一攻击由 Håstad 提出。</p>
|
||
<h4 id="原理-7"><a class="header" href="#原理-7">原理</a></h4>
|
||
<p>这里我们假设 e 为 3，并且加密者使用了三个不同的模数 $n_1,n_2,n_3$ 给三个不同的用户发送了加密后的消息 m，如下
|
||
$$ \begin{align} c_1 &=m^3\bmod n_1\ c_2&=m^3\bmod n_2\ c_3&=m^3\bmod n_3 \end{align} $$
|
||
这里我们假设 $n_1,n_2,n_3$ 互素，不然，我们就可以直接进行分解，然后得到 d，进而然后直接解密。
|
||
同时，我们假设 $m<n_i, 1\leq i \leq 3$。如果这个条件不满足的话，就会使得情况变得比较复杂，这里我们暂不讨论。
|
||
既然他们互素，那么我们可以根据中国剩余定理，可得$m^3 \equiv C \bmod n_1n_2n_3$。
|
||
此外，既然 $m<n_i, 1\leq i \leq 3$，那么我们知道 $m^3 < n_1n_2n_3$ 并且 $C<m^3 < n_1n_2n_3$，那么 $m^3 = C$，我们对 C 开三次根即可得到 m 的值。
|
||
对于较大的 e 来说，我们只是需要更多的明密文对。</p>
|
||
<h4 id="buuctf-rsa4"><a class="header" href="#buuctf-rsa4">BUUCTF-RSA4</a></h4>
|
||
<p><strong>题目</strong>
|
||
题目就给出了几个数字对
|
||
N = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
|
||
c = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243
|
||
N = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
|
||
c = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344
|
||
N = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
|
||
c = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242
|
||
<strong>解题</strong>
|
||
解题我们用脚本跑一下即可，但要注意此题所给的数都是5进制的。</p>
|
||
<h3 id="broadcast-attack-with-linear-padding"><a class="header" href="#broadcast-attack-with-linear-padding">Broadcast Attack with Linear Padding</a></h3>
|
||
<p>待补充</p>
|
||
<h3 id="related-message-attack"><a class="header" href="#related-message-attack">Related Message Attack</a></h3>
|
||
<h4 id="可攻击特征-9"><a class="header" href="#可攻击特征-9">可攻击特征</a></h4>
|
||
<p>当 Alice 使用同一公钥对两个具有某种线性关系的消息 M1 与 M2 进行加密，并将加密后的消息 C1，C2 发送给了 Bob 时，我们就可能可以获得对应的消息 M1 与 M2。这里我们假设模数为 N，两者之间的线性关系如下
|
||
$$ M_1 \equiv f(M_2) \bmod N $$
|
||
其中 f 为一个线性函数，比如说 $f=ax+b$。</p>
|
||
<h4 id="原理-8"><a class="header" href="#原理-8">原理</a></h4>
|
||
<p>首先，我们知道 $C_1 \equiv M_1 ^e \bmod N$，并且 $M_1 \equiv f(M_2) \bmod N$，那么我们可以知道 $M_2$ 是 $f(x)^e \equiv C_1 \bmod N$ 的一个解，即它是方程 $f(x)^e-C_1$ 在模 N 意义下的一个根。同样的，$M_2$ 是 $x^e - C_2$ 在模 N 意义下的一个根。所以说 $x-M_2$ 同时整除以上两个多项式。因此，我们可以求得两个多项式的最大公因子，如果最大公因子恰好是线性的话，那么我们就求得了 $M_2$。需要注意的是，在 $e=3$ 的情况下，最大公因子一定是线性的。
|
||
这里我们关注一下 $e=3$，且 $f(x)=ax+b$ 的情况。首先我们有
|
||
$$ C_1 \equiv M_1 ^3 \bmod N,M_1 \equiv aM_2+b \bmod N $$
|
||
那么我们有
|
||
$$ C_1 \equiv (aM_2+b)^3 \bmod N,C_2 \equiv M_2^3 \bmod N $$
|
||
我们需要明确一下我们想要得到的是消息 m，所以需要将其单独构造出来。
|
||
首先，我们有式 1
|
||
$$ (aM_2+b)^3=a^3M_2^3+3a^2M^2b+3aM_2b^2+b^3 $$
|
||
再者我们构造如下式 2
|
||
$$ (aM_2)^3-b^3 \equiv (aM_2-b)(a^2M_2^2+aM_2b+b^2) \bmod N $$
|
||
根据式 1 我们有
|
||
$$ a^3M_2^3-2b^3+3b(a^2M_2^2+aM_2b+b^2) \equiv C_1 \bmod N $$
|
||
继而我们有式 3
|
||
$$ 3b(a^2M_2^2+aM_2b+b^2) \equiv C_1-a^3C_2+2b^3 \bmod N $$
|
||
那么我们根据式 2 与式 3 可得
|
||
$$ (a^3C_2-b^3)*3b \equiv (aM_2-b)( C_1-a^3C_2+2b^3 ) \bmod N $$
|
||
进而我们有
|
||
$$ aM_2-b=\frac{3a^3bC_2-3b^4}{C_1-a^3C_2+2b^3} $$
|
||
进而
|
||
$$ aM_2\equiv \frac{2a^3bC_2-b^4+C_1b}{C_1-a^3C_2+2b^3} $$
|
||
进而
|
||
$$ M_2 \equiv\frac{2a^3bC_2-b^4+C_1b}{aC_1-a^4C_2+2ab^3}=\frac{b}{a}\frac{C_1+2a^3C_2-b^3}{C_1-a^3C_2+2b^3} $$
|
||
上面的式子中右边所有的内容都是已知的内容，所以我们可以直接获取对应的消息。
|
||
有兴趣的可以进一步阅读 A New Related Message Attack on RSA 以及 paper 这里暂不做过多的讲解。</p>
|
||
<h4 id="sctf-rsa3"><a class="header" href="#sctf-rsa3">SCTF-RSA3</a></h4>
|
||
<p><strong>题目链接</strong>https://github.com/ohroot/rsatools/tree/master/demos/sctf/rsa3
|
||
<strong>题目</strong>题目给出的是一个TCP的流量包，跟随数据流我们可以看到其中的N，user_id，密文C
|
||
<strong>解题</strong>我们取其中模N相同的0组和9组数据，按照上边的公式，写出解密脚本如下</p>
|
||
<pre><code>#!/usr/bin/env python3
|
||
import gmpy2
|
||
from Crypto.Util.number import long_to_bytes
|
||
id1 = 1002
|
||
id2 = 2614
|
||
c1 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c5bb724d1cee07e221e028d9b8bc24360208840fbdfd4794733adcac四5c38ad0225fde19a6a4c38e4207368f5902c871efdf1bdf4760b1a98ec1417893c8fce8389b6434c0fee73b13c284e8c9fb5c77e420a2b5b1a1c10b2a7a3545e95c1d47835c2718
|
||
c2 = 0x547995f4e2f4c007e6bb2a6913a3d685974a72b05bec02e8c03ba64278c9347d8aaaff672ad8460a8cf5bffa5d787c72722fe4fe5a901e2531b3dbcb87e5aa19bbceecbf9f32eacefe81777d9bdca781b1ec8f8b68799b4aa4c6ad120506222c7f0c3e11b37dd0ce08381fabf9c14bc74929bf524645989ae2df77c8608d0512c1cc四150765ab8350843b57a2464f848d8e08
|
||
n = 25357901189172733149625332391537064578265003249917817682864120663898336510922113258397441378239342349767317285221295832462413300376704507936359046120943334215078540903962128719706077067557948218308700143138420408053500628616299338204718213283481833513373696170774425619886049408103217179262264003765695390547355624867951379789924247597370496546249898924648274419164899831191925127182066301237673243423539604219274397539786859420866329885285232179983055763704201023213087119895321260046617760702320473069743688778438854899409292527695993045482549594428191729963645157765855337481923730481041849389812984896044723939553
|
||
a = 1
|
||
b = id1 - id2
|
||
</code></pre>
|
||
<h1 id="套公式"><a class="header" href="#套公式">套公式</a></h1>
|
||
<pre><code>def getmessage(a, b, c1, c2, n):
|
||
b3 = gmpy2.powmod(b, 3, n)
|
||
part1 = b * (c1 + 2 * c2 - b3) % n
|
||
part2 = a * (c1 - c2 + 2 * b3) % n
|
||
part2 = gmpy2.invert(part2, n)
|
||
return part1 * part2 % n
|
||
message = getmessage(a, b, c1, c2, n) - id2
|
||
print(long_to_bytes(message))
|
||
</code></pre>
|
||
<h3 id="coppersmiths-short-pad-attack"><a class="header" href="#coppersmiths-short-pad-attack">Coppersmith’s short-pad attack</a></h3>
|
||
<h4 id="可攻击特征-10"><a class="header" href="#可攻击特征-10">可攻击特征</a></h4>
|
||
<p>过短的padding长度导致的容易攻击</p>
|
||
<h3 id="known-high-bits-message-attackstereotyped-messages"><a class="header" href="#known-high-bits-message-attackstereotyped-messages">Known High Bits Message Attack(Stereotyped messages)</a></h3>
|
||
<h4 id="可攻击特征-11"><a class="header" href="#可攻击特征-11">可攻击特征</a></h4>
|
||
<ul>
|
||
<li>如果e较小，并且已知m的高位，则可通过此方法求出完整的m。</li>
|
||
<li>比如题目给出m=0x65c四6754a7776c8b88867e000000000000000000 前面的部分就是高位，后面的0就是低位，0只是占位的作用并不是真正m的值。</li>
|
||
</ul>
|
||
<h4 id="原理-9"><a class="header" href="#原理-9">原理</a></h4>
|
||
<p>知道了消息m的很大一部分$m_0$
|
||
现在，$c=(m_0+x)^e\mod n$，也就是 $f(x)=(m + x)^e - c$ 有一个解满足 $f(x)=k\cdot N(k=0,1,2\cdots)$ ,求解x。
|
||
依据coppersmith定理是可以求出剩下的所有明文部分。</p>
|
||
<h4 id="解题方法"><a class="header" href="#解题方法">解题方法</a></h4>
|
||
<p>在线sagemath：https://sagecell.sagemath.org/
|
||
自己安装的离线sage</p>
|
||
<h4 id="2019强网杯copperstudylevel1"><a class="header" href="#2019强网杯copperstudylevel1">2019强网杯copperstudy—level1</a></h4>
|
||
<p><strong>题目</strong>
|
||
n=0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953L
|
||
e=3
|
||
m=random.getrandbits(512)
|
||
c=pow(m,e,n)=0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1L
|
||
((m>>72)<<72)=0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000L
|
||
<strong>解题思路</strong>
|
||
要求求出完整的m，很明显e较小，并且已知了m的高位，我们通过CopperSmith算法的Stereotyped messages Attack获得完整的m。
|
||
<strong>解题脚本</strong></p>
|
||
<pre><code># exp.sage
|
||
load("coppersmith_py3.sage")
|
||
N = 0xa1888c641a05aeb81b3d1686317a86f104791fe1d570a5b11209f45d09ea401d255a70744e7a2d39520e359c23a9f1209ee47f496dbd279e62ee1648b3a277ced8825298274322e0a7a86deea282676310a73b6bb946fc924c34ac6c8784ff559bf9a004c03fb167ef54aaea90ce587f2f3074b40d7f632022ec8fb12e659953
|
||
e = 3
|
||
m = 0x9e67d3a220a3dcf6fc四742052621f543b8c78d5d9813e69272e65ac676672446e5c88887e8bfdfc92ec87ec74c16350e6b539e3bd910b000000000000000000
|
||
c = 0x93145ece45f416a11e5e9475518f165365456183c361500c2f78aff263028c90f20b7d97205f54e21f3bcc8a556b457889fde3719d0a0f9c9646f3f0d0a1e4bee0f259f023168fe8cc0511848c1635022fcc20b6088084585e2f8055a9d1b1d6bdb228087900bf7c6d42298f8e45c四51562c816e2303990834c94e580bf0cbd1
|
||
ZmodN = Zmod(N)
|
||
P.<x> = PolynomialRing(ZmodN)
|
||
f = (m + x)^e - c
|
||
dd = f.degree()
|
||
beta = 1
|
||
epsilon = beta / 7
|
||
mm = ceil(beta**2 / (dd * epsilon))
|
||
tt = floor(dd * mm * ((1/beta) - 1))
|
||
XX = ceil(N**((beta**2/dd) - epsilon))
|
||
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
|
||
print("结果是:", hex(roots[0])) # 注意输出结果是16进制数
|
||
</code></pre>
|
||
<p>运行方式：<code>sage exp.sage</code></p>
|
||
<h3 id="factoring-with-high-bits-known-attack"><a class="header" href="#factoring-with-high-bits-known-attack">Factoring with High Bits Known Attack</a></h3>
|
||
<h4 id="可攻击特征-12"><a class="header" href="#可攻击特征-12">可攻击特征</a></h4>
|
||
<ul>
|
||
<li>已知公钥中模数 N 的一个因子的较高位时，我们就有一定几率来分解 N，例如已知p的高位。</li>
|
||
</ul>
|
||
<h4 id="攻击方法-1"><a class="header" href="#攻击方法-1">攻击方法</a></h4>
|
||
<p>sage脚本</p>
|
||
<h4 id="2019强网杯copperstudylevel2"><a class="header" href="#2019强网杯copperstudylevel2">2019强网杯copperstudy—level2</a></h4>
|
||
<p><strong>题目</strong>
|
||
n=0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578dL
|
||
e=65537
|
||
m=random.getrandbits(512)
|
||
c=pow(m,e,n)=0x1922e7151c779d6bb554cba6a05858415e74739c36df0bcf169e49ef0e566a4353c51a306036970005f2321d1d104f91a673f40944e830619ed683d8f84eaf26e7a93c四abe1dbd7ca3babf3f4959def0e3d87f7818d54633a790fc74e9fed3c5b5456c21e3f425240f6217b0b14516cb59aa0ce74b83ca17d8cc四a0fbc829fb8L
|
||
((p>>128)<<128)=0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000L
|
||
<strong>解题脚本</strong></p>
|
||
<pre><code>n = 0x241ac918f708fff645d3d6e24315e5bb045c02e788c2b7f74b2b83484ce9c0285b6c54d99e2a601a386237d666db2805175e7cc86a733a97aeaab63486133103e30c1dca09741819026bd3ea8d08746d1d38df63c025c1793bdc7e38d194a30b492aadf9e31a6c1240a65db49e061b48f1f2ae949ac9e7e0992ed24f9c01578d
|
||
p_fake = 0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a873200000000000000000000000000000000
|
||
pbits = 1024
|
||
kbits = 130
|
||
pbar = p_fake & (2^pbits-2^kbits)
|
||
print("upper %d bits (of %d bits) is given" % (pbits-kbits, pbits))
|
||
PR.<x> = PolynomialRing(Zmod(n))
|
||
f = x + pbar
|
||
x0 = f.small_roots(X=2^kbits, beta=0.4)[0] # find root < 2^kbits with factor >= n^0.3
|
||
print(hex(int(x0 + pbar)))
|
||
</code></pre>
|
||
<p>计算结果：
|
||
➜ RSA-and-LLL-attacks sage factoring_with_high_bits_know.sage
|
||
upper 894 bits (of 1024 bits) is given
|
||
0x2c1e75652df018588875c7ab60472abf26a234bc1bfc1b685888fb5ded29ab5b93f5105c1e9b46912368e626777a87321efe89ec89bdf3e4d9da9a45df22a787</p>
|
||
<h3 id="boneh-and-durfee-attack"><a class="header" href="#boneh-and-durfee-attack">Boneh and Durfee attack</a></h3>
|
||
<h4 id="可攻击特征-13"><a class="header" href="#可攻击特征-13">可攻击特征</a></h4>
|
||
<p>当 d 较小时，满足$d < N^{0.292}$ 时，我们可以利用该攻击，比 Wiener’s Attack 要强一些。</p>
|
||
<h3 id="partial-key-exposure-attack"><a class="header" href="#partial-key-exposure-attack">Partial Key Exposure Attack</a></h3>
|
||
<h4 id="可攻击特征-14"><a class="header" href="#可攻击特征-14">可攻击特征</a></h4>
|
||
<ul>
|
||
<li>题目给出一组公钥n,e以及加密后的密文</li>
|
||
<li>若e较小，已知d的低位，则可通过此方法求出完整的d。</li>
|
||
</ul>
|
||
<h4 id="2019强网杯copperstudylevel3"><a class="header" href="#2019强网杯copperstudylevel3">2019强网杯copperstudy—level3</a></h4>
|
||
<p><strong>题目</strong>
|
||
n=0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3bL
|
||
e=3
|
||
m=random.getrandbits(512)
|
||
c=pow(m,e,n)=0x3d7e16fd8b0b1afdb4e12594c3d8590f1175800ef07bb275d7a8ad983d0d5d5fd5c6f81efa40f5d10c四8bb200f805e679d633ee584748e5feef003e0921dea736ba91eef72f3d591d3a54cd59fd36f61140fdd3fb2e2c028b684e50cbeae4a1f386f6ab35359d46a29996c0f7d9a4a189f1096150496746f064c3cc四1cf111b0L
|
||
d=invmod(e,(p-1)*(q-1))
|
||
d&((1<<512)-1)=0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749bL
|
||
<strong>解题脚本</strong></p>
|
||
<pre><code>def partial_p(p0, kbits, n):
|
||
PR.<x> = PolynomialRing(Zmod(n))
|
||
nbits = n.nbits()
|
||
f = 2^kbits*x + p0
|
||
f = f.monic()
|
||
roots = f.small_roots(X=2^(nbits//2-kbits), beta=0.3) # find root < 2^(nbits//2-kbits) with factor >= n^0.3
|
||
if roots:
|
||
x0 = roots[0]
|
||
p = gcd(2^kbits*x0 + p0, n)
|
||
return ZZ(p)
|
||
def find_p(d0, kbits, e, n):
|
||
X = var('X')
|
||
for k in range(1, e+1):
|
||
results = solve_mod([e*d0*X - k*X*(n-X+1) + k*n == X], 2^kbits)
|
||
for x in results:
|
||
p0 = ZZ(x[0])
|
||
p = partial_p(p0, kbits, n)
|
||
if p:
|
||
return p
|
||
if __name__ == '__main__':
|
||
# n(必须为整形才可计算) = 0x51fb3416aa0d71a430157d7c9853602a758e15462e7c08827b04cd3220c四27bbb8199ed4f5393dae43f013b68732a685defc17497f0912c886fa780dfacdfbb1461197d95a92a7a74ade874127a61411e14a901382ed3fb9d62c040c0dbaa374b5a4df06481a26da3fca271429ff10a4fc973b1c82553e3c1dd4f2f37dc24b3b
|
||
# d0=给出的部分d(必须为整形才可计算) = 0x17c四b18f1290b6a0886eaa7bf426485a3994c5b71186fe84d5138e18de7e060db57f9580381a917fdfd171bfd159825a7d1e2800e2774f5e4449d17e6723749b
|
||
e = 3
|
||
n = 57569201048993475052349187244752169754165154575782760003851777813767048953051839288528137121670999884309849815765999616346303792471518639080697166767644957046582385785721102370288806038187956032505761532789716009522131450217010629338000241936036185205038814391205848232364006349213836317806903032515194407739
|
||
nbits = n.nbits()
|
||
kbits = floor(nbits*0.5)
|
||
print("kbits : ", kbits)
|
||
d0 = 1244848677959253796774387650148978357579294769878147704641867595620534030329181934099194560059806799908134954814673426128260540575360296026444649631806619
|
||
print("lower %d bits (of %d bits) is given" % (kbits, nbits))
|
||
p = find_p(d0, kbits, e, n)
|
||
print("found p: %d" % p)
|
||
q = n//p
|
||
# print(d)
|
||
print("完整的d是:"+str(inverse_mod(e, (p-1))))
|
||
</code></pre>
|
||
<p><strong>计算结果</strong>
|
||
➜ RSA-and-LLL-attacks sage partial_key_exposure_attack.sage
|
||
kbits : 511
|
||
lower 511 bits (of 1023 bits) is given
|
||
found p: 7086179599191994333603836952445140343587486096628720220842297473373568276314821730585498733360983965734902690794828276489674036310720194369289757363461559
|
||
完整的d是:4724119732794662889069224634963426895724990731085813480561531648915712184209881153723665822240655977156601793863218850993116024207146796246193171575641039</p>
|
||
<h2 id="dp或dq泄漏攻击"><a class="header" href="#dp或dq泄漏攻击">dp或dq泄漏攻击</a></h2>
|
||
<h3 id="dpdq泄露"><a class="header" href="#dpdq泄露">dp&dq泄露</a></h3>
|
||
<h4 id="可攻击特征-15"><a class="header" href="#可攻击特征-15">可攻击特征</a></h4>
|
||
<p>已知 p, q, dp, dq, c求m。</p>
|
||
<h4 id="原理-10"><a class="header" href="#原理-10">原理</a></h4>
|
||
<p>dp本来是为了加速rsa加解密效率的,不过由于dp和p的关系相当密切,所以当dp泄漏也有相当大的危害
|
||
dp=d%(p-1)
|
||
dq=d%(q-1)
|
||
dp<em>e = 1 mod(p-1)
|
||
dq</em>e = 1 mod(q-1)</p>
|
||
<h4 id="buuctf-rsa1"><a class="header" href="#buuctf-rsa1">BUUCTF-RSA1</a></h4>
|
||
<p><strong>题目</strong>
|
||
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
|
||
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
|
||
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
|
||
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
|
||
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
|
||
<strong>解题</strong></p>
|
||
<pre><code>#!/usr/bin/python2
|
||
import gmpy2
|
||
from Crypto.Util.number import long_to_bytes
|
||
p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
|
||
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
|
||
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
|
||
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
|
||
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852
|
||
InvQ=gmpy2.invert(q,p)
|
||
mp=pow(c,dp,p)
|
||
mq=pow(c,dq,q)
|
||
m=(((mp-mq)*InvQ)%p)*q+mq
|
||
print(long_to_bytes(m))
|
||
</code></pre>
|
||
<h3 id="dp泄露"><a class="header" href="#dp泄露">dp泄露</a></h3>
|
||
<h4 id="可攻击特征-16"><a class="header" href="#可攻击特征-16">可攻击特征</a></h4>
|
||
<p>题目给出公钥n,e以及dp，给出密文要求解明文，我们可以通过n，e，dp求解私钥d。</p>
|
||
<h4 id="原理-11"><a class="header" href="#原理-11">原理</a></h4>
|
||
<p>推导过程参考：https://blog.csdn.net/weixin_45369385/article/details/109208109</p>
|
||
<h4 id="wustctf2020-dp_leaking"><a class="header" href="#wustctf2020-dp_leaking">WUSTCTF2020-dp_leaking</a></h4>
|
||
<p><strong>题目</strong>
|
||
e = 65537
|
||
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
|
||
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
|
||
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
|
||
<strong>解题脚本</strong></p>
|
||
<pre><code>from gmpy2 import invert,powmod
|
||
from Crypto.Util.number import long_to_bytes
|
||
e = 65537
|
||
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
|
||
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
|
||
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
|
||
for x in range(1, e):
|
||
if (e * dp % x == 1):
|
||
p = (e * dp - 1) // x + 1
|
||
if (n % p != 0):
|
||
continue
|
||
q = n // p
|
||
phin = (p - 1) * (q - 1)
|
||
d = invert(e, phin)
|
||
m = powmod(c, d, n)
|
||
if (len(hex(m)[2:]) % 2 == 1):
|
||
continue
|
||
print("m:", m)
|
||
print("flag:", long_to_bytes(m))
|
||
</code></pre>
|
||
<h2 id="rsa-选择明密文攻击"><a class="header" href="#rsa-选择明密文攻击">RSA 选择明/密文攻击</a></h2>
|
||
<h3 id="选择明文攻击"><a class="header" href="#选择明文攻击">选择明文攻击</a></h3>
|
||
<h3 id="任意密文解密"><a class="header" href="#任意密文解密">任意密文解密</a></h3>
|
||
<h3 id="rsa-parity-oracle"><a class="header" href="#rsa-parity-oracle">RSA parity oracle</a></h3>
|
||
<h3 id="rsa-byte-oracle"><a class="header" href="#rsa-byte-oracle">RSA Byte Oracle</a></h3>
|
||
<h3 id="rsa-parity-oracle-variant"><a class="header" href="#rsa-parity-oracle-variant">RSA parity oracle variant</a></h3>
|
||
<h3 id="padding-attack"><a class="header" href="#padding-attack">Padding Attack</a></h3>
|
||
<h4 id="可攻击特征-17"><a class="header" href="#可攻击特征-17">可攻击特征</a></h4>
|
||
<p>加密的Padding可控。</p>
|
||
<h4 id="例题"><a class="header" href="#例题">例题</a></h4>
|
||
<p><strong>题目</strong>
|
||
(‘n=’, ‘0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001dL’)
|
||
(‘e=’, ‘0x3’)
|
||
(‘c1=pow(hex_flag,e,n)’, ‘0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550L’)
|
||
(‘c2=pow(hex_flag+1,e,n)’, ‘0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3eL’)
|
||
<strong>解题分析</strong>
|
||
原理参考
|
||
https://www.anquanke.com/post/id/158944
|
||
意思很简单
|
||
1.pow(mm, e) != pow(mm, e, n)
|
||
2.利用rsa加密m+padding
|
||
值得注意的是，e=3，padding可控
|
||
那么我们拥有的条件只有
|
||
n,e,c,padding
|
||
所以这里的攻击肯定是要从可控的padding入手了
|
||
<strong>解题脚本</strong></p>
|
||
<pre><code>import gmpy2
|
||
from Crypto.Util.number import long_to_bytes
|
||
def getM2(a,b,c1,c2,n,e):
|
||
a3 = pow(a,e,n)
|
||
b3 = pow(b,e,n)
|
||
first = c1-a3*c2+2*b3
|
||
first = first % n
|
||
second = e*b*(a3*c2-b3)
|
||
second = second % n
|
||
third = second*gmpy2.invert(first,n)
|
||
third = third % n
|
||
fourth = (third+b)*gmpy2.invert(a,n)
|
||
return fourth % n
|
||
e=0x3
|
||
a=1
|
||
b=-1
|
||
c1=0x3aa5058306947ff46b0107b062d75cf9e497cdb1f120d02eaeca30f76492c550
|
||
c2=0x6a645739f25380a5e5b263ff5e5b4b9324381f6408a11fdaab0488209145fb3e
|
||
padding2=1
|
||
n=0xb33aebb1834845f959e05da639776d08a344abf098080dc5de04f4cbf4a1001d
|
||
m = getM2(a,b,c1,c2,n,e)-padding2
|
||
print(long_to_bytes(m))
|
||
</code></pre>
|
||
<h3 id="rsa-lsb-oracle-attack"><a class="header" href="#rsa-lsb-oracle-attack">RSA LSB Oracle Attack</a></h3>
|
||
<h4 id="可攻击特征-18"><a class="header" href="#可攻击特征-18"><strong>可攻击特征</strong></a></h4>
|
||
<p>可以选择密文并泄露最低位。
|
||
参考博客https://www.sohu.com/a/243246344_472906</p>
|
||
<h4 id="原理-12"><a class="header" href="#原理-12"><strong>原理</strong></a></h4>
|
||
<p>在一次RSA加密中，明文为m，模数为n，加密指数为e，密文为c。 我们可以构造出c’=((2^e)c)%n=((2^e)(m^e))%n=((2m)^e)%n， 因为m的两倍可能大于n，所以经过解密得到的明文是 m’=(2m)%n 。 我们还能够知道 m’ 的最低位lsb 是1还是0。 因为n是奇数，而2m是偶数，所以如果lsb 是0，说明(2m)%n 是偶数，没有超过n，即m<n/2.0，反之则m>n/2.0 。 举个例子就能明白2%3=2 是偶数，而4%3=1 是奇数。 以此类推，构造密文c“=(4^e)c)%n 使其解密后为m“=(4m)%n ，判断m“ 的奇偶性可以知道m 和 n/4 的大小关系。 所以我们就有了一个二分算法，可以在对数时间内将m的范围逼近到一个足够狭窄的空间。</p>
|
||
<h4 id="攻击脚本-1"><a class="header" href="#攻击脚本-1"><strong>攻击脚本</strong></a></h4>
|
||
<pre><code>def brute_flag(encrypted_flag, n, e):
|
||
flag_count = n_count = 1
|
||
flag_lower_bound = 0
|
||
flag_upper_bound = n
|
||
ciphertext = encrypted_flag
|
||
mult = 1
|
||
while flag_upper_bound > flag_lower_bound + 1:
|
||
sh.recvuntil("input your option:")
|
||
sh.sendline("D")
|
||
ciphertext = (ciphertext * pow(2, e, n)) % n
|
||
flag_count *= 2
|
||
n_count = n_count * 2 - 1
|
||
print("bit = %d" % mult)
|
||
mult += 1
|
||
sh.recvuntil("Your encrypted message:")
|
||
sh.sendline(str(ciphertext))
|
||
data=sh.recvline()[:-1]
|
||
if(data=='The plain of your decrypted message is even!'):
|
||
flag_upper_bound = n * n_count / flag_count
|
||
else:
|
||
flag_lower_bound = n * n_count / flag_count
|
||
n_count += 1
|
||
return flag_upper_bound
|
||
</code></pre>
|
||
<h2 id="rsa-侧信道攻击"><a class="header" href="#rsa-侧信道攻击">RSA 侧信道攻击</a></h2>
|
||
<h2 id="bleichenbachers-attack"><a class="header" href="#bleichenbachers-attack">Bleichenbacher’s attack</a></h2>
|
||
<p>PKCS 1.5 标准中可以伪造 RSA 签名
|
||
http://ddaa.tw/gctf_crypto_201_rsa_ctf_challenge.html</p>
|
||
<h2 id="附1公钥私钥获取信息"><a class="header" href="#附1公钥私钥获取信息">附1:公钥私钥获取信息</a></h2>
|
||
<h3 id="openssl"><a class="header" href="#openssl">OpenSSL</a></h3>
|
||
<p>OpenSSL是开源的的软件库包，其支持许多不同的加密算法。当然了其中有许多实用的工具，我们这里就使用其中有关RSA的部分。</p>
|
||
<h4 id="openssl-genrsa"><a class="header" href="#openssl-genrsa">openssl genrsa</a></h4>
|
||
<p>该命令生成一个RSA私钥。
|
||
➜ ~ openssl genrsa -h
|
||
usage: genrsa [args] [numbits] //密钥位数，建议在 2048bit 以上
|
||
-des encrypt the generated key with DES in cbc mode
|
||
-des3 encrypt the generated key with DES in ede cbc mode (168 bit key)
|
||
-aes128, -aes192, -aes256 encrypt PEM output with cbc aes
|
||
-camellia128, -camellia192, -camellia256 encrypt PEM output with cbc camellia
|
||
-out file 输出key到file //公钥可以从该私钥file中提取
|
||
-passout arg output file pass phrase source
|
||
-f4 use F4 (0x10001) for the E value
|
||
-3 use 3 for the E value</p>
|
||
<h4 id="openssl-rsa"><a class="header" href="#openssl-rsa">openssl rsa</a></h4>
|
||
<p>处理RSA密钥的格式转换等问题。
|
||
➜ ~ openssl rsa -h
|
||
Invalid cipher ‘h’
|
||
usage: rsa [-ciphername] [-check] [-in file] [-inform fmt]
|
||
[-modulus] [-noout] [-out file] [-outform fmt] [-passin src]
|
||
[-passout src] [-pubin] [-pubout] [-sgckey] [-text]
|
||
-check Check consistency of RSA private key # 检查输入密钥的正确性和一致性
|
||
-in file Input file (default stdin)
|
||
-inform format Input format (DER, NET or PEM (default)) # 输入文件格式，默认pem
|
||
-modulus Print the RSA key modulus # 输出模数
|
||
-noout Do not print encoded version of the key
|
||
-out file Output file (default stdout)
|
||
-outform format Output format (DER, NET or PEM (default PEM)) # 输出文件格式，默认pem
|
||
-passin src Input file passphrase source # 指定输入文件的加密口令，可来自文件、终端、环境变量等
|
||
-passout src Output file passphrase source
|
||
-pubin Expect a public key (default private key) # 指定输入文件是公钥
|
||
-pubout Output a public key (default private key)
|
||
-sgckey Use modified NET algorithm for IIS and SGC keys
|
||
-text Print in plain text in addition to encoded</p>
|
||
<h4 id="openssl-rsautl"><a class="header" href="#openssl-rsautl">openssl rsautl</a></h4>
|
||
<p>使用RSA密钥进行加密、解密、签名和验证等运算。</p>
|
||
<div class="table-wrapper"><table><thead><tr><th>数据补齐方式</th><th>输入数据长度</th><th>输出数据长度</th><th>参数字符串</th></tr></thead><tbody>
|
||
<tr><td>PKCS#1 v1.5</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-pkcs</td></tr>
|
||
<tr><td>PKCS#1 OAEP</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-oaep</td></tr>
|
||
<tr><td>PKCS#1 for SSLv23</td><td>少于(密钥长度-11)字节</td><td>同密钥长度</td><td>-ssl</td></tr>
|
||
<tr><td>不使用补齐</td><td>同密钥长度</td><td>同密钥长度</td><td>-raw</td></tr>
|
||
<tr><td>➜ ~ openssl rsautl -h</td><td></td><td></td><td></td></tr>
|
||
<tr><td>Usage: rsautl [options]</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-in file input file</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-out file output file</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-inkey file input key</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-keyform arg private key format - default PEM # 指定密钥格式</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-pubin input is an RSA public</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-certin input is a certificate carrying an RSA public key # 指定输入的是证书文件</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-ssl use SSL v2 padding # 使用SSLv23的填充方式</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-raw use no padding # 不进行填充</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-pkcs use PKCS#1 v1.5 padding (default)</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-oaep use PKCS#1 OAEP</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-sign sign with private key # 使用私钥做签名</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-verify verify with public key # 使用公钥认证签名</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-encrypt encrypt with public key # 使用公钥加密</td><td></td><td></td><td></td></tr>
|
||
<tr><td>-decrypt decrypt with private key # 使用私钥解密</td><td></td><td></td><td></td></tr>
|
||
</tbody></table>
|
||
</div>
|
||
<h4 id="openssl-加解密实例"><a class="header" href="#openssl-加解密实例">openssl 加解密实例</a></h4>
|
||
<p>生成私钥:<code>openssl genrsa -out prikey.pem</code>
|
||
查看私钥:<code>openssl rsa -in prikey.pem -text -modulus</code>
|
||
从私钥总提取公钥:<code>openssl rsa -in prikey.pem -pubout -out pubkey.pem</code>
|
||
查看公钥:<code>openssl rsa -in pubkey.pem -text -modulus -pubin</code>
|
||
加密:<code>openssl rsautl -encrypt -in file.plain -inkey pubkey.pem -pubin -out file.enc</code>
|
||
解密:(如有对应的补齐方式需要指定):<code>rsautl -decrypt -inkey prikey -in filename</code></p>
|
||
<h3 id="其他工具"><a class="header" href="#其他工具">其他工具</a></h3>
|
||
<h4 id="rsatools"><a class="header" href="#rsatools">rsatools</a></h4>
|
||
<p>使用使用p,q,e生成pem文件：<code>python rsatools.py -p p参数 -q q参数 -e e的值 -o prikey.pem</code></p>
|
||
<h4 id="rsactftool"><a class="header" href="#rsactftool">RsaCtfTool</a></h4>
|
||
<p>查看公钥的一些信息:<code>./RsaCtfTool.py --dumpkey --key ./key.pub</code>
|
||
已知公钥求私钥:<code>./RsaCtfTool.py --publickey ./key.pub --private</code>
|
||
已知公钥，自动解密:<code>./RsaCtfTool.py --publickey ./key.pub --uncipherfile filename</code>
|
||
已知 $n,e$ 生成公钥:<code>./RsaCtfTool.py --createpub -n 7828374823761928712873129873981723...12837182 -e 65537</code>
|
||
更多参看：https://github.com/Ganapati/RsaCtfTool</p>
|
||
<h4 id="2020西湖论剑-rsa-brokensystems"><a class="header" href="#2020西湖论剑-rsa-brokensystems">2020西湖论剑-RSA-BrokenSystems</a></h4>
|
||
<p><strong>题目</strong>
|
||
给了两个文件，message 和 public.key，还有一个脚本如下：</p>
|
||
<pre><code class="language-python">from Crypto.PublicKey import RSA
|
||
from Crypto.Cipher import PKCS1_OAEP
|
||
from secret import flag
|
||
import os
|
||
rsa = RSA.generate(2048)
|
||
public_key = rsa.publickey().exportKey()
|
||
f=open("public.key","w")
|
||
f.write(public_key.decode())
|
||
f.close()
|
||
rsakey=RSA.importKey(open("public.key","r").read())
|
||
rsa = PKCS1_OAEP.new(rsakey)
|
||
msg=rsa.encrypt(flag.encode())
|
||
f=open("message","wb")
|
||
f.write(msg)
|
||
f.close()
|
||
</code></pre>
|
||
<p><strong>解题思路</strong>
|
||
首先我们看一下公钥的一些参数：</p>
|
||
<pre><code class="language-bash">python RsaCtfTool.py --dumpkey --key ./2020ctf-BrokenSystems/public.key
|
||
private argument is not set, the private key will not be displayed, even if recovered.
|
||
n: 24493816160588971749455534346389861269947121809901305744877671102517333076424951483888863597563544011725032585417200878377314372325231470164799594965293350352923195632229495874587039720317200655351788887974047948082357232348155828924230567816817425104960545706688263839042183224681231800805037117758927837949941052360649778743187012198508745207332696876463490071925421229447425456903529626946628855874075846839745388326224970202749994059533831664092151570836853681204646481502222112116971464211748086292930029540995987019610460396057955900244074999111267618452967579699626655472948383601391620012180211885979095636919
|
||
e: 3683191938452247871641914583009119792552938079110383367782698429399084083048335018186915282465581498846777124014232879019914546010406868697694661244001972931366227108140590201194336470785929194895915077935083045957890179080332615291089360169761324533970721460473221959270664692795701362942487885620152952927112838769014944652059440137350285198702402612151501564899791870051001152984815689187374906618917967106000628810361686645504356294175173529719443860140795170776862320812544438211122891112138748710073230404456268507750721647637959502454394140328030018450883598342764577147457231373121223878829298942493059211583
|
||
</code></pre>
|
||
<p>可以看到这里边的e特别大，大家都说是用Wiener攻击可以解出，我还没尝试，想用RsaCtfTool试试看，所以小结下，本题有两种解法：</p>
|
||
<ul>
|
||
<li>常规思路解d –> 生成密钥key –> 解密</li>
|
||
<li>使用RsaCtfTool工具suoha
|
||
<strong>解题</strong>
|
||
使用RsaCtfTool爆破，我们可以看出该脚本最终用boneh_durfee爆破出了结果</li>
|
||
</ul>
|
||
<pre><code>python RsaCtfTool.py --publickey ./2020ctf-BrokenSystems/public.key --private
|
||
[*] Testing key ./2020ctf-BrokenSystems/public.key.
|
||
...省略暴力尝试的一部分内容...
|
||
[*] Performing roca attack on ./2020ctf-BrokenSystems/public.key.
|
||
[*] Performing pollard_p_1 attack on ./2020ctf-BrokenSystems/public.key.
|
||
[*] Performing boneh_durfee attack on ./2020ctf-BrokenSystems/public.key.
|
||
Results for ./2020ctf-BrokenSystems/public.key:
|
||
Private key :
|
||
-----BEGIN RSA PRIVATE KEY-----
|
||
MIIEXgIBAAKCAQEAwgdFIj/1uUss2EEhZvcoiiHyGH4aQhRTkYyrA8gCU0USM+sb
|
||
3CNjdEIoqoaUqMLLyDP4Dd9AgxpokBsjC四Pz8P7Uty0LlCteld7ayNzABHoq+5DI
|
||
...篇幅过长省略...
|
||
UWAvuuxI7lGac2B+/A/EcwBJfOT/qLCPpvFhA0Qje1HqlNSXc9e/FGt1UwxZkJBJ
|
||
JNGhlKRKaB0RJgJW5dA1jfyYU8xpPsDxfdDzLf2y167IbfqNNmL7ZF8IHj5+hPsB
|
||
0oVAN0gvoLxcOM2qMOXIt6aM
|
||
-----END RSA PRIVATE KEY-----
|
||
</code></pre>
|
||
<p>获得Private Key后，我们将该密钥保存为<code>pri.key</code>，使用openssl解出结果，需要注意的是解密时要指定填充模式为<code>PKCS1_OAEP</code></p>
|
||
<pre><code>cd 2020ctf-BrokenSystems && openssl rsautl -decrypt -oaep -in message -inkey pri.key
|
||
DASCTF{ce02347b86167f2d3519251b9a8a5ba8}
|
||
</code></pre>
|
||
<h3 id="rsa私钥文件修复"><a class="header" href="#rsa私钥文件修复">RSA私钥文件修复</a></h3>
|
||
<p>私钥文件修复可参考该帖子：https://code.felinae98.cn/CTF/Crypto/RSA-%E7%A7%81%E9%92%A5%E9%87%8D%E6%9E%84/</p>
|
||
<pre><code class="language-python">#!/usr/bin/python3
|
||
import re
|
||
from itertools import product
|
||
from Crypto.Util.number import GCD, inverse
|
||
def solve_linear(a, b, mod):
|
||
if a & 1 == 0 or b & 1 == 0:
|
||
return None
|
||
return (b * inverse(a, mod)) & (mod - 1) # 计算b*a^(-1)%mod
|
||
def to_n(s):
|
||
s = re.sub(r"[^0-9a-f]", "", s)
|
||
return int(s, 16)
|
||
def msk(s):
|
||
cleaned = "".join(map(lambda x: x[-2:], s.split(":"))) #去掉冒号和多余字符和空格
|
||
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
|
||
def msk_ranges(s): # 求每一个半字节的取值范围
|
||
return [range(16) if c == " " else [int(c, 16)] for c in s]
|
||
def msk_mask(s):
|
||
return int("".join("0" if c == " " else "f" for c in s), 16)
|
||
def msk_val(s):
|
||
return int("".join("0" if c == " " else c for c in s), 16)
|
||
N = to_n("""\
|
||
00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
|
||
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
|
||
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
|
||
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
|
||
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
|
||
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
|
||
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
|
||
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
|
||
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
|
||
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
|
||
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
|
||
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
|
||
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
|
||
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
|
||
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
|
||
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
|
||
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
|
||
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
|
||
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
|
||
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
|
||
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
|
||
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
|
||
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
|
||
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
|
||
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
|
||
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
|
||
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
|
||
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
|
||
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
|
||
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
|
||
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
|
||
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
|
||
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
|
||
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
|
||
e8:6c:1d""")
|
||
p_ranges, pmask_msk, pmask_val = msk("""\
|
||
0: e: : : :c :c : : : :b : : : : :
|
||
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
|
||
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
|
||
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
|
||
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
|
||
:b : :9 :e : :82:8d: : :13: : : a: a:
|
||
: :4 : :c : f: : :7 :e :0a: : : b: 5:
|
||
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
|
||
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
|
||
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
|
||
: d: : :7 : :93: : e:dc: : 0: :e7: :
|
||
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
|
||
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
|
||
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
|
||
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
|
||
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
|
||
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
|
||
: """)
|
||
q_ranges, qmask_msk, qmask_val = msk("""\
|
||
0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
|
||
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
|
||
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
|
||
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
|
||
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
|
||
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
|
||
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
|
||
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
|
||
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
|
||
a: : : :d : : :6b: 2: :9b: a:60: :d6:
|
||
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
|
||
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
|
||
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
|
||
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
|
||
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
|
||
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
|
||
1 :a :6 :8 : :60: :b3: : : :89: : :14:
|
||
:5 """)
|
||
_, dmask_msk, dmask_val = msk("""\
|
||
: : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
|
||
1:0d: :3 : :6 : : : b: : : :e : : :
|
||
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
|
||
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
|
||
b2: : :b :f :4 : : 8: :b : : : : 0: :
|
||
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
|
||
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
|
||
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
|
||
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
|
||
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
|
||
: : d:4 : :d : :6d: c:a :b6: : : : 1:
|
||
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
|
||
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
|
||
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
|
||
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
|
||
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
|
||
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
|
||
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
|
||
7:b : : : : :d9: 4: : e:c :68: : : :
|
||
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
|
||
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
|
||
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
|
||
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
|
||
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
|
||
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
|
||
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
|
||
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
|
||
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
|
||
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
|
||
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
|
||
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
|
||
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
|
||
:6 : : : :e0:c :3 : : : 3: : d: : :
|
||
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
|
||
0 :4 """)
|
||
_, dpmask_msk, dpmask_val = msk("""\
|
||
: 3:2a: : d: : : : :0 :1 : f: : : 6:
|
||
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
|
||
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
|
||
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
|
||
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
|
||
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
|
||
e: : : : : : :b :3a:5 : : : : : :
|
||
: : :cd:8 : : d: :7 : 3: : f:e : c: :
|
||
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
|
||
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
|
||
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
|
||
4: 1: : : : 8:46: : : : : : 0:f :c8:
|
||
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
|
||
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
|
||
2: : :47: :2 : 0:5 : : : d: 6:83: : :
|
||
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
|
||
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
|
||
55:61""")
|
||
_, dqmask_msk, dqmask_val = msk("""\
|
||
:0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
|
||
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
|
||
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
|
||
:d :21: :e : d: :c9:e : b: : :1 : : :
|
||
:d :a2:b7: : : :f3: :42: :e : c: :f :
|
||
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
|
||
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
|
||
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
|
||
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
|
||
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
|
||
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
|
||
: : : : : 1: :2 : :d1: : 6:e : d: :
|
||
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
|
||
: : :6 : : f: : : 0:6 : :51: :48:19:
|
||
: : :69:4 : c: :c : : f: :f4:d : : f:
|
||
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
|
||
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
|
||
1""")
|
||
E = 0x10001
|
||
def search(K, Kp, Kq, check_level, break_step):
|
||
max_step = 0
|
||
cands = [0] # 广搜队列
|
||
for step in range(1, break_step + 1):
|
||
# step代表复原倒数第step步
|
||
max_step = max(step, max_step)
|
||
mod = 1 << (4 * step)
|
||
mask = mod - 1
|
||
cands_next = []
|
||
for p, new_digit in product(cands, p_ranges[-step]):
|
||
pval = (new_digit << ((step - 1) * 4)) | p
|
||
# 四个剪枝
|
||
if check_level >= 1:
|
||
qval = solve_linear(pval, N & mask, mod)
|
||
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
|
||
continue
|
||
if check_level >= 2:
|
||
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
|
||
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
|
||
continue
|
||
if check_level >= 3:
|
||
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
|
||
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
|
||
continue
|
||
if check_level >= 4:
|
||
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
|
||
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
|
||
continue
|
||
if pval * qval == N: #得到答案
|
||
print("Kq =", Kq)
|
||
print("pwned")
|
||
print("p =", pval)
|
||
print("q =", qval)
|
||
p = pval
|
||
q = qval
|
||
d = inverse(E, (p - 1) * (q - 1))
|
||
print("d =", d)
|
||
coef = inverse(p, q)
|
||
from Crypto.PublicKey import RSA
|
||
print(RSA.construct((N, E, d, p, q, coef)).exportKey().decode())
|
||
quit()
|
||
cands_next.append(pval)
|
||
if not cands_next:
|
||
return False
|
||
cands = cands_next
|
||
return True
|
||
def check_val(val, mask, mask_msk, mask_val):
|
||
test_mask = mask_msk & mask
|
||
test_val = mask_val & mask
|
||
return val & test_mask == test_val
|
||
for K in range(1, E):
|
||
if K % 100 == 0:
|
||
print("checking", K)
|
||
if search(K, 0, 0, check_level=2, break_step=20):
|
||
print("K =", K)
|
||
break
|
||
for Kp in range(1, E):
|
||
if Kp % 1000 == 0:
|
||
print("checking", Kp)
|
||
if search(K, Kp, 0, check_level=3, break_step=30):
|
||
print("Kp =", Kp)
|
||
break
|
||
for Kq in range(1, E):
|
||
if Kq % 100 == 0:
|
||
print("checking", Kq)
|
||
if search(K, Kp, Kq, check_level=4, break_step=9999):
|
||
print("Kq =", Kq)
|
||
break
|
||
</code></pre>
|
||
<pre><code class="language-sh">openssl rsautl -decrypt -inkey private.pem -keyform PEM -in flag.enc -oaep
|
||
</code></pre>
|
||
<p><strong>题目</strong></p>
|
||
<h3 id="rsa-私钥恢复和最优非对称加密填充jarvis-oj-god-like-rsa"><a class="header" href="#rsa-私钥恢复和最优非对称加密填充jarvis-oj-god-like-rsa">RSA 私钥恢复和最优非对称加密填充(Jarvis OJ-God Like RSA)</a></h3>
|
||
<p>题目给出了三个文件，加密后的 flag<code>flag.enc</code>，残缺的私钥<code>private.corrupted</code>，公钥<code>pubkey.pem</code>
|
||
<a href="https://gitcode.net/dnrops/rsa_ctf_problems/-/raw/master/godlikeRSA.rar">godlikeRSA</a>
|
||
解题可参考：<a href="https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html">https://www.40huo.cn/blog/rsa-private-key-recovery-and-oaep.html</a></p>
|
||
<pre><code class="language-python">import re
|
||
import pickle
|
||
from itertools import product
|
||
from libnum import invmod, gcd
|
||
from Crypto.PublicKey import RSA
|
||
def solve_linear(a, b, mod):
|
||
if a & 1 == 0 or b & 1 == 0:
|
||
return None
|
||
return (b * invmod(a, mod)) & (mod - 1) # hack for mod = power of 2
|
||
def to_n(s):
|
||
s = re.sub(r"[^0-9a-f]", "", s)
|
||
return int(s, 16)
|
||
def msk(s):
|
||
cleaned = "".join(map(lambda x: x[-2:], s.split(":")))
|
||
return msk_ranges(cleaned), msk_mask(cleaned), msk_val(cleaned)
|
||
def msk_ranges(s):
|
||
return [range(16) if c == " " else [int(c, 16)] for c in s]
|
||
def msk_mask(s):
|
||
return int("".join("0" if c == " " else "f" for c in s), 16)
|
||
def msk_val(s):
|
||
return int("".join("0" if c == " " else c for c in s), 16)
|
||
E = 65537
|
||
N = to_n("""00:c0:97:78:53:45:64:84:7d:8c:c4:b4:20:e9:33:
|
||
58:67:ec:78:3e:6c:f5:f0:5c:a0:3e:ee:dc:25:63:
|
||
d0:eb:2a:9e:ba:8f:19:52:a2:67:0b:e7:6e:b2:34:
|
||
b8:6d:50:76:e0:6a:d1:03:cf:77:33:d8:b1:e9:d7:
|
||
3b:e5:eb:1c:65:0c:25:96:fd:96:20:b9:7a:de:1d:
|
||
bf:fd:f2:b6:bf:81:3e:3e:47:44:43:98:bf:65:2f:
|
||
67:7e:27:75:f9:56:47:ba:c4:f0:4e:67:2b:da:e0:
|
||
1a:77:14:40:29:c1:a8:67:5a:8f:f5:2e:be:8e:82:
|
||
31:3d:43:26:d4:97:86:29:15:14:a9:69:36:2c:76:
|
||
ed:b5:90:eb:ec:6f:ce:d5:ca:24:1c:aa:f6:63:f8:
|
||
06:a2:62:cb:26:74:d3:5b:82:4b:b6:d5:e0:49:32:
|
||
7b:62:f8:05:c4:f7:0e:86:59:9b:f3:17:25:02:aa:
|
||
3c:97:78:84:7b:16:fd:1a:f5:67:cf:03:17:97:d0:
|
||
c6:69:85:f0:8d:fa:ce:ee:68:24:63:06:24:e1:e4:
|
||
4c:f8:e9:ad:25:c7:e0:c0:15:bb:b4:67:48:90:03:
|
||
9b:20:7f:0c:17:eb:9d:13:44:ab:ab:08:a5:c3:dc:
|
||
c1:98:88:c5:ce:4f:5a:87:9b:0b:bf:bd:d7:0e:a9:
|
||
09:59:81:fa:88:4f:59:60:6b:84:84:ad:d9:c7:25:
|
||
8c:e8:c0:e8:f7:26:9e:37:95:7c:e1:48:29:0f:51:
|
||
e7:bd:98:2f:f6:cc:80:e7:f0:32:0b:89:51:92:4e:
|
||
c2:6d:50:53:2b:3b:77:72:d1:bd:1a:1f:92:d7:12:
|
||
79:61:61:c5:a4:7e:b3:85:eb:f0:7c:6d:46:03:c5:
|
||
e6:d5:81:2c:ba:7e:ea:8d:51:7d:63:55:34:2a:b6:
|
||
d4:dc:31:5a:f1:99:e3:dc:8c:83:0b:a2:2a:d5:3c:
|
||
41:48:41:54:1a:a9:e8:b6:70:bf:d3:fe:ed:19:17:
|
||
14:94:13:b3:17:e3:8b:8e:6f:53:ed:e2:44:e8:4a:
|
||
32:d6:5c:0d:a8:80:f5:fc:02:e9:46:55:d5:a4:d3:
|
||
e7:c6:30:77:f9:73:e9:44:52:d8:13:9d:5d:bf:9e:
|
||
fa:3a:b5:96:79:82:5b:cd:19:5c:06:a9:00:96:fd:
|
||
4c:a4:73:88:1a:ec:3c:11:de:b9:3d:e0:50:00:1e:
|
||
ac:21:97:a1:96:7d:6b:15:f9:6c:c9:34:7f:70:d7:
|
||
9d:2d:d1:48:4a:81:71:f8:12:dd:32:ba:64:31:60:
|
||
08:26:4b:09:22:03:83:90:17:7f:f3:a7:72:57:bf:
|
||
89:6d:e4:d7:40:24:8b:7b:bd:df:33:c0:ff:30:2e:
|
||
e8:6c:1d""")
|
||
p_ranges, pmask_msk, pmask_val = msk(""" 0: e: : : :c :c : : : :b : : : : :
|
||
:ab: e: 2: 8:c : : : 1:6 :6 : 6: f:d9: 0:
|
||
8 :5c:7 :06: : : :0 : 3:5 :4b: :6 : : :
|
||
2 : :6 : : : :2 :bc: c: :85:1 : 1:d : 3:
|
||
1:b4: : b: 1: 3: d:a : : :6e: 0:b :2 : :
|
||
:b : :9 :e : :82:8d: : :13: : : a: a:
|
||
: :4 : :c : f: : :7 :e :0a: : : b: 5:
|
||
: e:91:3 : :3c: 9: : 6: : :b5:7d: 1: :
|
||
: : :b :a1:99:6 :4 :3 :c :1a:02:4 : : 9:
|
||
9 :f : d:bd: :0 : : : :b3: : 4: :e9: 9:
|
||
: d: : :7 : :93: : e:dc: : 0: :e7: :
|
||
e : :2 : b: 2:5 : : : : : c:5f: : :e2:
|
||
: : 9: :2a: : e: : :2 : :9f: 7:3 : :
|
||
b : f:b : : 8: 7: : :f :6 :e :c : :3 : :
|
||
f7: 5: 8: 5: : : : : : 8: e: :03: c: :
|
||
33:76:e : 1:7 : c: : 0: :0b: : a: : 2: 9:
|
||
:c8:bf: : :06: 7:d5: :02: c:b :e2: 7:2 :
|
||
: """)
|
||
q_ranges, qmask_msk, qmask_val = msk(""" 0: f: :d0: 1:55: 4:31: : b:c4:8 : : e: d:
|
||
34: 3:f : : : : : 8:99:1 : : a:0 : :4 :
|
||
0 : :f : :a4:41:2 : :a : : 1: : a: c: :
|
||
: : 9: : : 2:f4: f: : : : :1 : 4:9 :
|
||
a : : :79:0 : : : : : 2: 8:b : :4 : 8:
|
||
:9b: 1: :d : :f :e4: :4 :c :e : :3 : :
|
||
7:2 : :d :8 :2 :7 : :d :67:fc:e : 0:f9: 7:
|
||
8 : : : :1 :2f: :51: : :2e:0a: e:3d: 6:
|
||
b : :dd: : 0:fb: :f4: : : :b4: 9:c : :
|
||
a: : : :d : : :6b: 2: :9b: a:60: :d6:
|
||
0:4f:16:d1: : :5 :fc: :f : :8 : : : :
|
||
1: 6:e1:9 : e:4 : 6: c: d:d :73: 3: : :7 :
|
||
:8 : 9: :3b:f : 2: : :f1: e: : :1e: :
|
||
8 : : : 6:0 : 4:99:e : : 5: : : 4: : :
|
||
: a:81:64: :7 :f : 9: d: :9 : : 7:93:f :
|
||
ac:8c: : 8: : 0: d: 8: :7 : :1d: :f : :
|
||
1 :a :6 :8 : :60: :b3: : : :89: : :14:
|
||
:5 """)
|
||
_, dmask_msk, dmask_val = msk(""" : : : f:8 :a5:d : 2: 0:b :7 : : 1: : 4:
|
||
1:0d: :3 : :6 : : : b: : : :e : : :
|
||
0e: 0:db: :1a:1c:c0: : e: : :99:bc:8 :a5:
|
||
7 :7 :7 : b: : : 8: 8: :7 :55: 2: : :f :
|
||
b2: : :b :f :4 : : 8: :b : : : : 0: :
|
||
0 : :6 :9 : : : : b: 4: : 0: a: 5:07:b :
|
||
9: c:9a: 9: : 7:9e: : b:60:f : : : :0 :
|
||
: 3:0 : : : : 1:b : : : b: 6:0 :f : :
|
||
: 2:18: 6: b:1 : : : : :d3:f3: :a : :
|
||
3: : : : : 3: d: 1: 2:7 : : d: : 2: d:
|
||
: : d:4 : :d : :6d: c:a :b6: : : : 1:
|
||
69: : 7: :89: :c :8 :61: d:25: 3:7 :1b: 4:
|
||
b : :8 :55: :49: 1:2 :3 : :1 :e9:a8: 3: :
|
||
9 : : 1:f8:d3: :e : :d : :9 :b6: : :71:
|
||
1 : :c1: : b: 1: : 6:e : :64: : :1a:c :
|
||
: b: :bf:c : : 0: : 8:a :4 : :26:a :5 :
|
||
6 : : : :eb: :e5: a: :3e:f9:10:0 : : :
|
||
6:0 : : 8: : 1:72: c:0 : f:5 : f:9c: 0: e:
|
||
7:b : : : : :d9: 4: : e:c :68: : : :
|
||
c: :3a: : :a0:ea: 3: 4: :72:a :d : 8: :
|
||
:0d:5 :0 : a: 7:c :bb: 6: 4:a :ce:d :2 : 1:
|
||
: :17:6 : : c: b: : f: :3 : 5:6 :3 :0e:
|
||
: 7:c :3e: 2: 9: 7: 6: f: e: f: 9: :f3: 9:
|
||
a :c1:6 : : 1:9 : :43: : f: 5: :0 :27: 4:
|
||
4 :a : :e9: : 8: 4:3 :8a: 6:16:d5:c : e: e:
|
||
:d : c:b :a8: : 7: : 9: :7 :7d: : : :
|
||
: : :4 :2 : : 3: 3: 6: : : :7b:0 : :
|
||
e: :0 : :a : : 5: : : : 5:1 :82:c :0d:
|
||
4 :2 :fd:36: 5:50:0 : : :d : f: 6: : :e :
|
||
0 : : :ce: :9e:8 : :0 :d :07:b3: : : :
|
||
0 :e4: : :68:b :c : : c:5 : : :3 : 7: 2:
|
||
c:e0: :5 : : :b4: :ef: 7: :1 :e : 0:f :
|
||
:6 : : : :e0:c :3 : : : 3: : d: : :
|
||
3: 3: c: a: :b : a:71: 3: 0:a : :4 :5d: :
|
||
0 :4 """)
|
||
_, dpmask_msk, dpmask_val = msk(""" : 3:2a: : d: : : : :0 :1 : f: : : 6:
|
||
1 :2 :1b:07: a:e :b :c5:58:7 : :e8: 7: 1: c:
|
||
: 1:b :a0: 4:0f:5 :67: :3 :7 :6 :f9: : c:
|
||
:79: 0:1 :65: :8 : :99: d:d : :2 :9 :0 :
|
||
e: :0 : : : : d: :d :7 :6 :a9: a:8b: b:
|
||
: : 7: a:37: : :7 :1 :6 : :c2: 7:6 :b :
|
||
e: : : : : : :b :3a:5 : : : : : :
|
||
: : :cd:8 : : d: :7 : 3: : f:e : c: :
|
||
: a: :c : f:c : 7:b :5 : : :2 :8 :8 :6 :
|
||
0a: a: : :3 :db: : 4:00: : d: :b : 5: :
|
||
20: 2: 5: :82: : 0: 6: :8a: :7 : : 8: :
|
||
4: 1: : : : 8:46: : : : : : 0:f :c8:
|
||
2 : : c:7 : : 1: : :2 : 0: 5: : : 1:9b:
|
||
6:9 : 0:74: :c : :e : : :cb:b :3 :3 : :
|
||
2: : :47: :2 : 0:5 : : : d: 6:83: : :
|
||
:c7: : :0b: : : c: :3 :8 : :9 :4 : 7:
|
||
5 :c0:fe: :f9: 1: :0 : e: 8:02: : f: :c :
|
||
55:61""")
|
||
_, dqmask_msk, dqmask_val = msk(""" :0b:7 :4 :0 : 0:6 : 7:7e: : 5: : 7: : a:
|
||
a :d : 0: 6: 4:86: : :8 : : : : :e :8f:
|
||
9: : : : 1: :2 : : 7: b:1 :5 : f: :8 :
|
||
:d :21: :e : d: :c9:e : b: : :1 : : :
|
||
:d :a2:b7: : : :f3: :42: :e : c: :f :
|
||
: 0:f :7 : 4: 5:34: :4 : c: : :8 :d : 8:
|
||
5 :af: 3:1d: 5:4 : :2 : :6 :c : 6:a :1 :5 :
|
||
a:9 : :d : : :0a:a1: :f :7 :9 :b : : :
|
||
f:2 :27: f: :0 :f6:4d: : : : : :5 : :
|
||
4:08: : 5: : 8: 5: : : :18: 4: 8:57: 2:
|
||
f: a: : :a8: f: c:f : e: 1:9 :c : 4:9 : :
|
||
: : : : : 1: :2 : :d1: : 6:e : d: :
|
||
: f:04:2 :8d: : 3: : :b : 8: :d6: : 2:
|
||
: : :6 : : f: : : 0:6 : :51: :48:19:
|
||
: : :69:4 : c: :c : : f: :f4:d : : f:
|
||
d:0 :0d:b :3 : 3:2 : : :6 : b:5 :2 : : c:
|
||
1:5a: f:f : : :7e:3e: :d :f :0 : d: c: 6:
|
||
1""")
|
||
def search(K, Kp, Kq, check_level, break_step):
|
||
max_step = 0
|
||
cands = [0]
|
||
for step in range(1, break_step + 1):
|
||
#print " ", step, "( max =", max_step, ")"
|
||
max_step = max(step, max_step)
|
||
mod = 1 << (4 * step)
|
||
mask = mod - 1
|
||
cands_next = []
|
||
for p, new_digit in product(cands, p_ranges[-step]):
|
||
pval = (new_digit << ((step - 1) * 4)) | p
|
||
if check_level >= 1:
|
||
qval = solve_linear(pval, N & mask, mod)
|
||
if qval is None or not check_val(qval, mask, qmask_msk, qmask_val):
|
||
continue
|
||
if check_level >= 2:
|
||
val = solve_linear(E, 1 + K * (N - pval - qval + 1), mod)
|
||
if val is None or not check_val(val, mask, dmask_msk, dmask_val):
|
||
continue
|
||
if check_level >= 3:
|
||
val = solve_linear(E, 1 + Kp * (pval - 1), mod)
|
||
if val is None or not check_val(val, mask, dpmask_msk, dpmask_val):
|
||
continue
|
||
if check_level >= 4:
|
||
val = solve_linear(E, 1 + Kq * (qval - 1), mod)
|
||
if val is None or not check_val(val, mask, dqmask_msk, dqmask_val):
|
||
continue
|
||
if pval * qval == N:
|
||
print("Kq =", Kq)
|
||
print("pwned")
|
||
print("p =", pval)
|
||
print("q =", qval)
|
||
p = pval
|
||
q = qval
|
||
d = invmod(E, (p - 1) * (q - 1))
|
||
coef = invmod(p, q)
|
||
print (RSA.construct(map(int, (N, E, d, p, q, coef))).exportKey())
|
||
quit()
|
||
cands_next.append(pval)
|
||
if not cands_next:
|
||
return False
|
||
cands = cands_next
|
||
return True
|
||
def check_val(val, mask, mask_msk, mask_val):
|
||
test_mask = mask_msk & mask
|
||
test_val = mask_val & mask
|
||
return val & test_mask == test_val
|
||
# K = 4695
|
||
# Kp = 15700
|
||
# Kq = 5155
|
||
for K in range(1, E):
|
||
if K % 100 == 0:
|
||
print ("checking", K)
|
||
if search(K, 0, 0, check_level=2, break_step=20):
|
||
print ("K =", K)
|
||
break
|
||
for Kp in range(1, E):
|
||
if Kp % 1000 == 0:
|
||
print ("checking", Kp)
|
||
if search(K, Kp, 0, check_level=3, break_step=30):
|
||
print ("Kp =", Kp)
|
||
break
|
||
for Kq in range(1, E):
|
||
if Kq % 100 == 0:
|
||
print ("checking", Kq)
|
||
if search(K, Kp, Kq, check_level=4, break_step=9999):
|
||
print ("Kq =", Kq)
|
||
break
|
||
</code></pre>
|
||
<h4 id="最优非对称加密填充"><a class="header" href="#最优非对称加密填充">最优非对称加密填充</a></h4>
|
||
<pre><code class="language-python">from Crypto.PublicKey import RSA
|
||
from Crypto.Cipher import PKCS1_OAEP
|
||
with open('pubkey.pem', 'r') as f:
|
||
key = RSA.importKey(f)
|
||
N = key.n
|
||
e = key.e
|
||
print(N)
|
||
print(e)
|
||
with open('private.pem', 'r') as f:
|
||
private = RSA.importKey(f)
|
||
oaep = PKCS1_OAEP.new(private)
|
||
with open('flag.enc', 'r') as f:
|
||
print(oaep.decrypt(f.read()))
|
||
</code></pre>
|
||
<h2 id="已知p-q-e-求-n"><a class="header" href="#已知p-q-e-求-n">已知p q e 求 n</a></h2>
|
||
<pre><code class="language-python"># 已知p q e 求 n
|
||
# 在一次RSA密钥对生成中，假设p=473398607161，q=4511491，e=17
|
||
import gmpy2
|
||
p = 473398607161
|
||
q = 4511491
|
||
e = 17
|
||
n = (p-1)*(q-1)
|
||
d = gmpy2.invert(e,n)
|
||
print(d)
|
||
</code></pre>
|
||
<h2 id="附2rsa综合性题集"><a class="header" href="#附2rsa综合性题集">附2:RSA综合性题集</a></h2>
|
||
<h2 id="附3参考资料"><a class="header" href="#附3参考资料">附3:参考资料</a></h2>
|
||
<p>RSA知识大纲：https://ctf-wiki.github.io/ctf-wiki/crypto/asymmetric/rsa/rsa_theory-zh/
|
||
大质数在线分解数据库：http://factordb.com
|
||
一类RSA：https://www.jianshu.com/p/0272069cb936?utm_campaign=maleskine
|
||
对模数N的一些小结：https://nonuplebroken.com/2018/11/26/RSA模数相关攻击/#原理
|
||
Jarvis-OJ-Crypto: https://skysec.top/2017/12/11/Jarvis-OJ-Crypto/#very-hard-RSA
|
||
对RSA的总结1：https://zhuanlan.zhihu.com/p/76228394
|
||
对RSA的总结2：https://xz.aliyun.com/t/6459#toc-59</p>
|
||
|
||
</main>
|
||
|
||
<nav class="nav-wrapper" aria-label="Page navigation">
|
||
<!-- Mobile navigation buttons -->
|
||
<a rel="prev" href="../../posts/ctf/3.1_Crypto.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
||
<i class="fa fa-angle-left"></i>
|
||
</a>
|
||
|
||
<a rel="next prefetch" href="../../posts/ctf/3.5_Base64.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
||
<i class="fa fa-angle-right"></i>
|
||
</a>
|
||
|
||
<div style="clear: both"></div>
|
||
</nav>
|
||
</div>
|
||
</div>
|
||
|
||
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
||
<a rel="prev" href="../../posts/ctf/3.1_Crypto.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
||
<i class="fa fa-angle-left"></i>
|
||
</a>
|
||
|
||
<a rel="next prefetch" href="../../posts/ctf/3.5_Base64.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
||
<i class="fa fa-angle-right"></i>
|
||
</a>
|
||
</nav>
|
||
|
||
</div>
|
||
|
||
|
||
|
||
<script>
|
||
window.playground_line_numbers = true;
|
||
</script>
|
||
|
||
<script>
|
||
window.playground_copyable = true;
|
||
</script>
|
||
|
||
<script src="../../ace.js"></script>
|
||
<script src="../../editor.js"></script>
|
||
<script src="../../mode-rust.js"></script>
|
||
<script src="../../theme-dawn.js"></script>
|
||
<script src="../../theme-tomorrow_night.js"></script>
|
||
|
||
<script src="../../elasticlunr.min.js"></script>
|
||
<script src="../../mark.min.js"></script>
|
||
<script src="../../searcher.js"></script>
|
||
|
||
<script src="../../clipboard.min.js"></script>
|
||
<script src="../../highlight.js"></script>
|
||
<script src="../../book.js"></script>
|
||
|
||
<!-- Custom JS scripts -->
|
||
<script src="../../src/js/custom.js"></script>
|
||
|
||
|
||
</div>
|
||
</body>
|
||
</html>
|