Various Scattered Known Bits Challs
Adapted from https://github.com/y011d4/factor-from-random-known-bits
Rust:
use rug::{ops::Pow, Integer};
use std::collections::VecDeque;
fn str_to_vec(bits_str: &[u8]) -> Vec<i8> {
let bit_len = bits_str.len();
let mut bits: Vec<i8> = vec![];
for i in 0..bit_len {
if bits_str.len() < i + 1 {
bits.push(0);
continue;
}
match bits_str[bits_str.len() - i - 1] as char {
'0' => bits.push(0),
'1' => bits.push(1),
_ => bits.push(-1),
};
}
bits
}
fn bits_to_num(bits: &Vec<i8>, n: i32, saved: &Integer, saved_idx: i32) -> Integer {
let two = Integer::from_str_radix("2", 10).unwrap();
let mut ret = saved.clone();
for i in (saved_idx as usize + 1)..(n as usize) {
assert_ne!(bits[i], -1);
if bits[i] == 1 {
ret += two.clone().pow(i as u32) * bits[i]
}
}
return ret;
}
fn check(p: &Integer, q: &Integer, n: &Integer, m: u32) -> bool {
let two = Integer::from_str_radix("2", 10).unwrap();
let two_pow = two.clone().pow(m);
let mut tmp_n = p.clone();
tmp_n *= q;
tmp_n %= &two_pow;
let mut n_two_pow = n.clone();
n_two_pow %= &two_pow;
return tmp_n == n_two_pow;
}
pub fn factor_bfs(
n: &Integer,
p_bits: Vec<i8>,
q_bits: Vec<i8>,
verbose: bool,
) -> Option<(Integer, Integer)> {
let mut ans: Option<(Integer, Integer)> = None;
let bit_len = p_bits.len().max(q_bits.len());
let mut queue: VecDeque<((Vec<i8>, Integer), (Vec<i8>, Integer), i32)> = VecDeque::new();
queue.push_back((
(p_bits, "0".parse().unwrap()),
(q_bits, "0".parse().unwrap()),
-1,
));
let mut fixed_idx: i32;
let two = Integer::from_str_radix("2", 10).unwrap();
while queue.len() != 0 {
let tmp = queue.pop_front().unwrap();
let (p_bits, saved_p) = tmp.0;
let (q_bits, saved_q) = tmp.1;
let saved_idx = tmp.2;
let mut idx = 0.max(saved_idx);
while idx < bit_len as i32 {
if p_bits[idx as usize] == -1 || q_bits[idx as usize] == -1 {
break;
}
idx += 1;
}
fixed_idx = idx - 1;
if verbose {
print!(
"\rSearched index: {:<8?} Queue size: {:<8?}",
fixed_idx,
queue.len()
);
}
let tmp_p: Integer = bits_to_num(&p_bits, fixed_idx + 1, &saved_p, saved_idx);
let tmp_q: Integer = bits_to_num(&q_bits, fixed_idx + 1, &saved_q, saved_idx);
let two_pow = two.clone().pow((fixed_idx + 1) as u32);
let mut tmp_n = tmp_p.clone();
tmp_n *= &tmp_q;
if &tmp_n == n {
ans = Some((tmp_p, tmp_q));
break;
}
tmp_n %= &two_pow;
let mut n_two_pow = n.clone();
n_two_pow %= &two_pow;
if tmp_n != n_two_pow {
continue;
}
if fixed_idx + 1 == bit_len as i32 {
continue;
}
let tmp_p_two_pow = match p_bits[idx as usize] {
-1 => {
let mut ret = tmp_p.clone();
ret += &two_pow;
ret
}
_ => "0".parse().unwrap(),
};
let tmp_q_two_pow = match q_bits[idx as usize] {
-1 => {
let mut ret = tmp_q.clone();
ret += &two_pow;
ret
}
_ => "0".parse().unwrap(),
};
if (p_bits[idx as usize] == -1) && (q_bits[idx as usize] == -1) {
if check(&tmp_p, &tmp_q, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_0 = p_bits.clone();
tmp_p_bits_0[idx as usize] = 0;
let mut tmp_q_bits_0 = q_bits.clone();
tmp_q_bits_0[idx as usize] = 0;
queue.push_back((
(tmp_p_bits_0, tmp_p.clone()),
(tmp_q_bits_0, tmp_q.clone()),
fixed_idx + 1,
));
}
if check(&tmp_p, &tmp_q_two_pow, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_0 = p_bits.clone();
tmp_p_bits_0[idx as usize] = 0;
let mut tmp_q_bits_1 = q_bits.clone();
tmp_q_bits_1[idx as usize] = 1;
queue.push_back((
(tmp_p_bits_0, tmp_p.clone()),
(tmp_q_bits_1, tmp_q_two_pow.clone()),
fixed_idx + 1,
));
}
if check(&tmp_p_two_pow, &tmp_q, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_1 = p_bits.clone();
tmp_p_bits_1[idx as usize] = 1;
let mut tmp_q_bits_0 = q_bits.clone();
tmp_q_bits_0[idx as usize] = 0;
queue.push_back((
(tmp_p_bits_1, tmp_p_two_pow.clone()),
(tmp_q_bits_0, tmp_q.clone()),
fixed_idx + 1,
));
}
if check(&tmp_p_two_pow, &tmp_q_two_pow, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_1 = p_bits.clone();
tmp_p_bits_1[idx as usize] = 1;
let mut tmp_q_bits_1 = q_bits.clone();
tmp_q_bits_1[idx as usize] = 1;
queue.push_back((
(tmp_p_bits_1, tmp_p_two_pow),
(tmp_q_bits_1, tmp_q_two_pow),
fixed_idx + 1,
));
}
} else if p_bits[idx as usize] == -1 {
let tmp_q_next = match q_bits[(fixed_idx + 1) as usize] {
0 => tmp_q.clone(),
1 => {
let mut ret = tmp_q.clone();
ret += two_pow;
ret
}
_ => panic!(),
};
if check(&tmp_p, &tmp_q_next, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_0 = p_bits.clone();
tmp_p_bits_0[idx as usize] = 0;
queue.push_back((
(tmp_p_bits_0, tmp_p.clone()),
(q_bits.clone(), tmp_q_next.clone()),
fixed_idx + 1,
));
}
if check(&tmp_p_two_pow, &tmp_q_next, &n, (fixed_idx + 2) as u32) {
let mut tmp_p_bits_1 = p_bits.clone();
tmp_p_bits_1[idx as usize] = 1;
queue.push_back((
(tmp_p_bits_1, tmp_p_two_pow.clone()),
(q_bits.clone(), tmp_q_next.clone()),
fixed_idx + 1,
));
}
} else if q_bits[idx as usize] == -1 {
let tmp_p_next = match p_bits[(fixed_idx + 1) as usize] {
0 => tmp_p.clone(),
1 => {
let mut ret = tmp_p.clone();
ret += two_pow;
ret
}
_ => panic!(),
};
if check(&tmp_p_next, &tmp_q, &n, (fixed_idx + 2) as u32) {
let mut tmp_q_bits_0 = q_bits.clone();
tmp_q_bits_0[idx as usize] = 0;
queue.push_back((
(p_bits.clone(), tmp_p_next.clone()),
(tmp_q_bits_0, tmp_q.clone()),
fixed_idx + 1,
));
}
if check(&tmp_p_next, &tmp_q_two_pow, &n, (fixed_idx + 2) as u32) {
let mut tmp_q_bits_1 = q_bits.clone();
tmp_q_bits_1[idx as usize] = 1;
queue.push_back((
(p_bits.clone(), tmp_p_next.clone()),
(tmp_q_bits_1, tmp_q_two_pow.clone()),
fixed_idx + 1,
));
}
} else {
panic!("panic");
}
}
if verbose {
println!();
}
ans
}
fn test_1() {
let n: Integer = "323".parse().unwrap();
let p_bits = str_to_vec(b"_____");
let q_bits = str_to_vec(b"___1_");
println!("{:?}", factor_bfs(&n, p_bits.clone(), q_bits.clone(), true).unwrap());
}
fn test_2() {
// Randomsum - Firebird Internal CTF 2023
let n: Integer = "23972924803656725645946104612288180239254366533835447570211958435888835149024704127730216635918366064642338427956144263722073485986182242950506562077115261972266819566896991605805331175926336936623727858956342095970617971414648408199255433214266089182676417304576439449775708611349397255997892478936263800821533938404508818638694040349742659681140030800595271768949111564030020912493782604042297523251856213731597666043107228963973074577037344345426025975807448211052650699923918471883180836394144595630503970610793789138051476548955355193194759840128264687246565426588680843522246453634852078525991710060236523993541".parse().unwrap();
let p_bits = str_to_vec(b"110_010_01101__10_10_11_0__00100_1__1_1010_000__1_00_0__0000_1_011__10_01__1001_1__0_01_01_001_1_10_1_1_01_10_10110______0_0010_00_1000__101110001000000_1110____101_1___0_0110_0_0___11111_1___1_0_110_0_01_00__01__111__1___0_110_0_00__00_10100_11__11_100_01___000___11_0___1001_00_11_0001011_11_00_110110110_11_1_0_0_0_0_0110___1__0_11110111___0111_00_00_101_01_1111_1_00_0_1111_0110_1__000_1101__1_0__1011_0100_1__11101000_0101_1______0__01_0_110_010010111110100_01_0_110011000_0___0_000110__10101__0100___10_1_011010_101__0101__10_0__1110001_1101_1__1__011110_10__1__11101__011_0_11_1110_0__0__11010____10__1010_0_00111_0__10_00_____1_110011_0__00__110_11000__10_01_00__0011101_1_1111_000__1_11_0_01100111__00_10011_01_000001101____0100___01___0001__110010__10_0_1011__1_11_11_00_0_0_00_11000_01_1_00101_000_11__0_1_1____0_0100010_1_1_1_0_10_0___110_11_0_01_1__1__010111____0_1_101_10111011001011_1000010____0101_1__0_1_01___11___10__1000_01_1_0__101_100_1__1_0___00_111_1_0111011_1____1_11_1_0001110__1_1111___00011_0_11__");
let q_bits = str_to_vec(b"1_1101_000____11110_01__0_00110_01_0000_00101___10011000_00_10_1__00__101_0_0_11_00001__1__1_10_1_00_01_0_0__00__01100_00_101101__1__110_01_0_11_10101_10_00110_0__110_10___01_1____10101_01_00_1__1110011100_111_10__00101_00____1_0_10_00__011_01_0__0000100__0__111___0_11100__00_11_111_11_10_1__01_10110_00_____00__1111000_1_01_1110_1000011111___10_0_00000_0_11_0__11100_01111_111_01_01011001000_01010_110_0_1_111__1_011_0_110_1_0101__00_01001110_000_100011___00___010__0_110_010_00_10__00_101__110_11_0100_1110_11_1_10_0_0___110_01__1_01_1_00_1___00_0__00_001___0_0_____01_110100_110_1000_1_1__0_10_0100__00___01_00_______010_0_001_01_1__1_110__001010__1____011__10_101_1101000_1___01__0___0011111_11_1_100_____10_1_11__11_1_001_10_____0111__01_1_01110__0_00_0011_1__01__011___01_110_0000_11_0_0_11110_0__11___110__0_0_01_1101_1_10__01_0010011__1__10_1_0_1_0_1_01_10__111_0_1011111_0_01__10_00_1___01_1_011_1110__10001_1_10001__01_0010_0110110__1_111110011__1_0110_0_10_0_00_1_0____0_100__0101__100011_11__1_10_10_1___001_001");
println!("{:?}", factor_bfs(&n, p_bits.clone(), q_bits.clone(), true).unwrap());
}
fn test_3() {
// Shibs - mapnaCTF 2024
let n: Integer = "20316898932195904153277570911129808751568815578115203862825426326247688399447840960418077345063791379522152467572219078649052797300815169624324245983590614914067269781160218800744443132820786495383622657350005442865119235171347222481549171383138463856866590153226706585323109487068718209302113471433380661465050751463957327192775767168671487596946840993911799696944069759277414133632444513772210700794949276020219498655982617016744321984479076362225276288530893635176013522707993482886351558163399233902562390621254309853983712254751850630385079750216639722676398376824903099579116864460998259826947136455660974737633".parse().unwrap();
let p_bits = str_to_vec(b"111_0_1_1110_1__01__0_00_1_0___01110_1_0__11_101____01__1_______100001110_01_1__1__0_1__110_101__01101_1_0_111__1___1__1_11_0_10__11111_1_0__1101_1___0_0__10_____01111_1101_10_1__10_0_0__1110110__110_1_1___101__10__1__1_110_011_010001_1_1__1110_10__1_1__01____010111_0111_10_1__11_1____011101___10_01_1___1_00_01__1_01_001_101_11__01_0_1__011__11__1_1__11____11_001_0010_01_0__01_1__00100110___1__10_00__0_11_01__1_100_1101_0_100011___00__00__11__001__10_0__11__1001_0_0_10____1_0_0111__010___00_10_1100_011_11000_1_1_1010_101_11110___1______110__10__0__1_001_01_11_1_1_11___01_0_1111__10100_11_11_1111_100_1111__1_1_0_11_110_11001___1__0___111__1_0_0_01_1_0_11_11_1_1_1100_100101110_01_111_11_11_1011011100111_0101__001011__01_11_0_0__100_0010_1_1_1010_1_1_11_11_1_0_0111_10111110__10_011_00_1001_1011111_111_1011_01_0100___1011_1_0__111___11_0_1_1111_0_1_01_00_0_1__011_11101011__1___00__1_0_1001_10101_011_1_10_11__1_1___1111_1_1_0011_0_010__1_0101___0__001__0_1__0100110_0_11__0_______1___1011_0_1_1__00_1_1__10__0_1___1");
let q_bits = str_to_vec(b"101_1_0_111__1___1__1_11_0_10__11111_1_0__1101_1___0_0__10_____01111_1101_10_1__10_0_0__1110110__110_1_1___101__10__1__1_110_011_010001_1_1__1110_10__1_1__01____010111_0111_10_1__11_1____011101___10_01_1___1_00_01__1_01_001_101_11__01_0_1__011__11__1_1__11____11_001_0010_01_0__01_1__00100110___1__10_00__0_11_01__1_100_1101_0_100011___00__00__11__001__10_0__11__1001_0_0_10____1_0_0111__010___00_10_1100_011_11000_1_1_1010_101_11110___1______110__10__0__1_001_01_11_1_1_11___01_0_1111__10100_11_11_1111_100_1111__1_1_0_11_110_11001___1__0___111__1_0_0_01_1_0_11_11_1_1_1100_100101110_01_111_11_11_1011011100111_0101__001011__01_11_0_0__100_0010_1_1_1010_1_1_11_11_1_0_0111_10111110__10_011_00_1001_1011111_111_1011_01_0100___1011_1_0__111___11_0_1_1111_0_1_01_00_0_1__011_11101011__1___00__1_0_1001_10101_011_1_10_11__1_1___1111_1_1_0011_0_010__1_0101___0__001__0_1__0100110_0_11__0_______1___1011_0_1_1__00_1_1__10__0_1___1111_0_1_1110_1__01__0_00_1_0___01110_1_0__11_101____01__1_______100001110_01_1__1__0_1__110_101__01");
println!("{:?}", factor_bfs(&n, p_bits.clone(), q_bits.clone(), true).unwrap());
}
fn test_4() {
// this_is_rsa - seccon 2020
let n: Integer = "13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657".parse().unwrap();
let p_bits = str_to_vec(b"0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____");
let q_bits = str_to_vec(b"0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____");
println!("{:?}", factor_bfs(&n, p_bits.clone(), q_bits.clone(), true).unwrap());
}
fn test_5() {
// regulus_calendula - hsctf 8
let n: Integer = "1070967922573882179692417367760420248456309713636439677513784737168798065507455125054690578149877073001572069002425729373797930733547750551400937636148971182969016272792822140103164779636336219915058989702373595895562942798667787668311267634837988264341819013654747333733422170781760297381018182461433787586377152297670011962997360422616868800134658314712129513816494813763728585344076962461314551325853100195636469366749177012032772638158979073276461027166349205437288667713822553000765151973215112878105194608990688155578357437031358928188020980709430856641483258154513163581590236992179566092627029173654407478509082715970006577586099880672105727945701894441148354173020461062571220683791863288555411212394785676166615770790140949436014247954539177005137973703301608916876584966511877310482533373226365431511627119790635073627503926678816724220796141762057169550724772373260930363251813701900759329341333531480079995245106812127214375255520736882666539315413158223865784187826023921267843052297763651750750998641156388010350564473894879259529320746217208168754737990729258083314644682404982670770719331558659278463113066604944478085594684477803558559057716120122505611554338015548743871605602897574909935805177978608484648849579290221331608525746268227952052491351881682216549911805395119521348576611612242957486024975838562356647211156701908471749066099784735037587125508000077791759300952028930521248611865850443269734966662959614699445203941262204478440284578704176140100488375118917022510842969011570034924994598944592282314072863144333881651667437771181400406696057247573300264473239471837968966933011326742847590569021782619315035004899172425231074650455325502292266363693271341991380569863082490337686939056852367733798934354875215559899176583714615894369269329066683103208700882183848411072258552050466775118099722028575925215126083599297620878410897166191888806279331534471667213799162520410842273037948001529457572610445124074038426102939195951155838983607256758051787060617914924480049209211140045443710546124169800114641091804253566275878540582924332711936871786315983506979248233452900949798324272682449237687499274489363136798687207921945618867721123863075792221617629300446229261314425919564680175902354644992995227367034699542386920884784163877250187632436523687933553247252679763219316814361385525316113378672425093325811232360647196987087279305325674321368522492688274835478928742344800906113203667514697084403775196451487973527172203783497673107".parse().unwrap();
let p_bits = str_to_vec(b"1111101110011000110010010___0___0___0___11010___0___0___10100___1111100111000___11011101101111100___101011010___110011010___10110___0___111110100___0___0___0___0___0___110010000___10101001110011011010111011110___0___10010___101110010___11000___0___11110___10000___0___0___1010100011001101111111110___11100___1011101010010___0___0___0___0___10010___10010___0___0___0___11110___0___10100___1011100111000___11000___100110010___0___11111110101010110___0___0___0___0___11010___0___10010___11010___11110___1100111110100___0___0___1010111110010___0___0___11000___10100___0___11000___0___101111100___0___0___0___0___10010___0___0___0___0___0___10110___10100___1000110110000___1001111011110___11110___0___11110___10100___110110100___10100___0___0___111111111010101011110___101110000___0___0___10111101101011110___0___100011011100111010000___0___11100___0___0___0___0___1101101110100___0___0___0___0___0___11011110100010000___0___10010___0___10000___0___1111100011001011100110010___11110___0___0___0___0___0___0___0___0___101110000___0___10000___11110___11010___0___0___111011100___0___11010___0___0___111110000___0___1111101011010___1000111010010___10010___0___0___0___10010___0___0___0___0___10010___1110110010000___0___0___101111010___101011110___0___10011101101010010___11010___11110___0___111110110___0___10100___0___10000___11000___111111110___10000___0___0___0___0___10000___11000___0___11010___0___0___11000___10110___0___11001110111011100___0___10110___111111100___10010___0___10011101101111010___10010___1100111010010___0___0___10010___10100___0___0___0___100011010___0___0___0___11001101110110001001111010010___11010___0___0___101110100___0___0___11100___111111001000101011000___11100___0___0___0___0___0___11000___0___0___0___0___101110010___0___0___111111110___101011001011110111111011100111000___110010010___0___10010___0___0___11010___0___0___0___111111010___10110___0___0___0___11010___0___0___1101100010010___0___0___0___0___100111111100100110110___0___100111100___0___110111110___11100___0___0___111011110___0___111010110___10110___10110___10011101110011100___11010___100111110___0___0___1010110010110___1000100011110___0___110011110___0___0___10010___11111110110011110___0___0___0___100110010___110111110___0___10010___11110___1101101111100___1110101011100___100110000___0___0___0___100110110___0___10000___0___110111000___100011110___0___0___0___10111010110010110___0___0___110010000___0___0___0___10010___0___0___1110101111111000101111010___11010___0___1000101011000___1101100111110___0___0___1001101110010___0___1000101110100___1111101110110___0___0___0___0___0___0___0___0___110110110___10000___10010___0___0___0___111010000___10010___0___110111111000110011100___0___0___10000___0___110011110___1110111110000___0___11010___11110___0___0___0___11110___0___0___0___1100110010000___11110___11000___1010111111010___11100___10000___0___11010___1111111011110___0___0___0___101011100___0___101011000___111110000___0___0___0___1010110010110___10001011110011110___11110___0___0___0___0___11101111101111110___0___11010___0___0___0___110011110___11100___0___10000___11000___100011101011110110011011111110001110101111100___11110___10010___0___10110___11000___111011110___10010___1000100111010___11010___0___11110___0___0___0___1110110110110___0___101111100___0___11100___0___10100___10010___0___0___10110___0___111111110___100010000___0___1101100110010___10010___10001000110011000___11111000110010110___0___1000111010100___11100___10110___10110___11110___0___1010111111110___0___11110___0___0___101111000___0___10010___0___110111110___10100___10000___0___111011111011110011000___0___0___101111011101100010010___11010___0___0___111011110___11100___0___11000___110011010___1010101111110___11000___0___0___10000___10100___0___0___11100___100011010___0___10110___0___11010___10100___0___10000___0___10010___1010100011000___101111000___11000___0___1101111111110___0___101010101101111110000___0___0___110010100___0___0___111110000___0___0___0___101011110___0___0___110011110___10110___0___0___0___10110___1001101010010___10100___101011010___0___101110100___0___11000___10010___10000___0___11010___1011");
let q_bits = str_to_vec(b"1111111111000___101011010___0___110011100___0___110111000___100111101001101010110___0___10000___0___0___101110000___0___0___0___11010___110111110___0___11110___10011011111110100___0___10000___0___0___10100___0___0___10110___0___101010000___0___0___100110110___100111110___0___101111100___0___0___110010110___111011010___0___0___11111001101111010___110010100___0___111011110___0___0___0___0___111010100___110010001010110111000___11100___0___0___1011100010000___11111011111011111100101111001100111111001111100111110___11111011110110000___0___0___110011110___10110___0___0___0___11000___0___110010000___10010___110111000___111011000___0___0___0___0___0___10110___10010___111011010___11110___11001000111011000___0___0___10110___101111100___10100___11000___10000___0___0___10110___0___111110100___10000___10110___11101010110011010___0___0___10001111110110100___0___10100___0___0___10110___111010100___0___0___10110___0___0___1000111110100___0___0___11100___101010000___0___0___11010___0___11010___10000___1100100110101111100111110___0___0___0___11000___10000___10100___10100___0___0___111110010___10000___10011010111110010___1010111111000___0___10110___10000___0___0___0___100010100___10000___0___11110___0___0___0___0___0___0___100110110___10010___0___0___0___11011011111110010___11110___0___0___0___1011100111110___111110010___100011000___0___0___1000110110010___1111101110100___0___0___11100___101010000___0___10110___0___11011111101111011111110110000___10100___0___0___11010___0___10100___11100___110010111010110010010___0___100011010___11110___1100111011011011101010000___0___0___0___0___10010___0___10100___10010___101011100___1100101010000___0___0___0___11100___0___10110___11010___10100___0___0___111010100___0___11100___11100___10000___0___110010110___0___0___0___0___0___0___10000___100011010___100111100___11110___0___1100111010010___0___10110___0___0___10100___11001101111011100___0___0___10010___0___0___11010___10100___0___1110100011110___0___11110___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___10101111100011100___0___11100___0___0___0___0___0___100110110___1101101110110___0___11110___10000___101011010___0___1110111111100___0___11110___111011010___100110010___101111010___0___0___1010111111111001111110110___0___11000___11010___0___11011010101110100___0___0___10100___10100___0___10000___0___0___10110___10010___0___0___0___0___11110___100111000___0___1100110111110___11010___0___11010___0___0___0___11110___0___0___10110___0___0___0___0___0___0___0___100010110___100011001001100110100___0___0___10000___0___0___0___110110000___10000___0___111111000___0___10011111110111010___100111110___0___0___0___110010000___101110100___111110100___1010111111100___0___0___110011100___0___11101111111110110___10010___10000___111110101010111110110___0___0___100011100___100010010___1101101111101101111011111000111111110___0___1101110011010___1011100011111101111011000___0___0___111111001111100010000___0___1010100010000___0___11100___0___10110___0___0___0___0___0___0___10100___0___100011010___10000___111011001010111011011010110010000___0___110011110___11100___11101100111010010___0___11100___111010010___0___11100___0___0___10100___0___111110110___0___11101110100110100___0___0___0___0___0___10110___0___1011101011110___111011100___111110010___0___0___0___11001100111011000___10010___0___100010000___0___0___11100___0___1110111010110___10110___10100___10110___0___0___0___10100___11110___10010___11100___111110010___101111100___0___10110___0___0___0___0___0___100010010___0___11110___0___101010000___0___0___101011110___111011110___100111000___0___0___10110___0___0___0___0___10110___0___0___1010101011101100100110101001110111000___101111000___101010100___0___0___0___10110___11110___10000___111111010___0___10010___10100___11100___0___11111001110011100___10011111110110111011101110000___10000___10110___10100___0___100110110___0___0___0___11000___0___0___11000___0___0___10100___101011100___111110100___11100___11100___0___111111000___0___110010010___0___0___0___10010___0___0___1001100111111111110011110___0___10100___0___101111100___111110010___11010___0___0___0___101010011001");
println!("{:?}", factor_bfs(&n, p_bits.clone(), q_bits.clone(), true).unwrap());
}
fn main() {
test_1();
test_2();
test_3();
test_4();
test_5();
}
Python rewrite:
from Crypto.Util.number import long_to_bytes
def bits_to_num(bits, n, saved, saved_idx):
ret = saved
for i in range(saved_idx + 1, n):
assert bits[i] != -1
if bits[i] == 1:
ret += 2**i * bits[i]
return ret
def check(p, q, n, m):
two_pow = 2**m
return (p*q) % two_pow == n % two_pow
def str_to_vec(x):
ret = []
for i in x:
if i == '1':
ret.append(1)
elif i == '0':
ret.append(0)
elif i == '_':
ret.append(-1)
return ret[::-1]
def factor_bfs(n, p_bits, q_bits):
p_bits = str_to_vec(p_bits)
q_bits = str_to_vec(q_bits)
bit_len = max(len(p_bits), len(q_bits))
queue = [[(p_bits, 0), (q_bits, 0), -1]]
while len(queue) != 0:
(p_bits, saved_p), (q_bits, saved_q), saved_idx = queue[0]
queue = queue[1:]
idx = max(0, saved_idx)
while idx < bit_len:
if p_bits[idx] == -1 or q_bits[idx] == -1:
break
idx += 1
fixed_idx = idx - 1
print(
f"\rSearched index: {fixed_idx}/{bit_len-1} Queue size: {len(queue)}",
end=""
)
tmp_p = bits_to_num(p_bits, fixed_idx + 1, saved_p, saved_idx)
tmp_q = bits_to_num(q_bits, fixed_idx + 1, saved_q, saved_idx)
two_pow = 2 ** (fixed_idx+1)
tmp_n = tmp_p * tmp_q
if tmp_n == n:
print()
return tmp_p, tmp_q
if tmp_n % two_pow != n % two_pow or fixed_idx + 1 == bit_len:
continue
tmp_p_two_pow = tmp_p + two_pow if p_bits[idx] == -1 else 0
tmp_q_two_pow = tmp_q + two_pow if q_bits[idx] == -1 else 0
if p_bits[idx] == -1 and q_bits[idx] == -1:
if check(tmp_p, tmp_q, n, fixed_idx + 2):
tmp_p_bits_0 = p_bits.copy(); tmp_p_bits_0[idx] = 0
tmp_q_bits_0 = q_bits.copy(); tmp_q_bits_0[idx] = 0
queue.append([(tmp_p_bits_0, tmp_p), (tmp_q_bits_0, tmp_q), fixed_idx+1])
if check(tmp_p, tmp_q_two_pow, n, fixed_idx + 2):
tmp_p_bits_0 = p_bits.copy(); tmp_p_bits_0[idx] = 0
tmp_q_bits_1 = q_bits.copy(); tmp_q_bits_1[idx] = 1
queue.append([(tmp_p_bits_0, tmp_p), (tmp_q_bits_1, tmp_q_two_pow), fixed_idx+1])
if check(tmp_p_two_pow, tmp_q, n, fixed_idx + 2):
tmp_p_bits_1 = p_bits.copy(); tmp_p_bits_1[idx] = 1;
tmp_q_bits_0 = q_bits.copy(); tmp_q_bits_0[idx] = 0
queue.append([(tmp_p_bits_1, tmp_p_two_pow),(tmp_q_bits_0, tmp_q),fixed_idx + 1])
if check(tmp_p_two_pow, tmp_q_two_pow, n, fixed_idx + 2):
tmp_p_bits_1 = p_bits.copy(); tmp_p_bits_1[idx] = 1
tmp_q_bits_1 = q_bits.copy(); tmp_q_bits_1[idx] = 1
queue.append([(tmp_p_bits_1, tmp_p_two_pow), (tmp_q_bits_1, tmp_q_two_pow), fixed_idx+1])
elif p_bits[idx] == -1:
tmp_q_next = tmp_q if q_bits[fixed_idx+1] == 0 else tmp_q + two_pow
if check(tmp_p, tmp_q_next, n, fixed_idx + 2):
tmp_p_bits_0 = p_bits.copy(); tmp_p_bits_0[idx] = 0
queue.append([(tmp_p_bits_0, tmp_p), (q_bits.copy(), tmp_q_next), fixed_idx+1])
if check(tmp_p_two_pow, tmp_q_next, n, fixed_idx + 2):
tmp_p_bits_1 = p_bits.copy(); tmp_p_bits_1[idx] = 1
queue.append([(tmp_p_bits_1, tmp_p_two_pow), (q_bits.copy(), tmp_q_next), fixed_idx+1])
elif q_bits[idx] == -1:
tmp_p_next = tmp_p if p_bits[fixed_idx+1] == 0 else tmp_p + two_pow
if check(tmp_p_next, tmp_q, n, fixed_idx + 2):
tmp_q_bits_0 = q_bits.copy(); tmp_q_bits_0[idx] = 0
queue.append([(p_bits.copy(), tmp_p_next), (tmp_q_bits_0, tmp_q), fixed_idx+1])
if check(tmp_p_next, tmp_q_two_pow, n, fixed_idx + 2):
tmp_q_bits_1 = q_bits.copy(); tmp_q_bits_1[idx] = 1
queue.append([(p_bits.copy(), tmp_p_next), (tmp_q_bits_1, tmp_q_two_pow), fixed_idx+1])
else:
raise Exception
print()
return (0, 0)
def test_1():
n = 323
p_bits = "_____"
q_bits = "___1_"
print(factor_bfs(n, p_bits, q_bits))
def test_2():
# Randomsum - Firebird Internal CTF 2023
import random
random.seed(1337)
n = 23972924803656725645946104612288180239254366533835447570211958435888835149024704127730216635918366064642338427956144263722073485986182242950506562077115261972266819566896991605805331175926336936623727858956342095970617971414648408199255433214266089182676417304576439449775708611349397255997892478936263800821533938404508818638694040349742659681140030800595271768949111564030020912493782604042297523251856213731597666043107228963973074577037344345426025975807448211052650699923918471883180836394144595630503970610793789138051476548955355193194759840128264687246565426588680843522246453634852078525991710060236523993541
e = 65537
t = 14000066433047292246448752794201977165563733655047203575867121262166187560566711892325594792129845153282249633931642143973215540568376319171334159461972160877466256238242152503653373908684017280676080125004854850332445723153614845802146395899581463896936557611606222767193353523987995818833578861773617167644193038121558267674251210114195760011821306729346761634659759967871454608623374306270379642305886119902085577927092579512468263725679201030921437666386689058685094677660425920780030296995254804923997961573399239884517270135267952236745232513979074599714453057660939074051865674834210296195715452442772175320306
c = 6629119219609628910262885521069144816410786299451464969111007624958603576922839074850618464009859754669933262329186876226112761547177882680972685257697161919090897947135355903504454390331332951864051787079151186147963687429869735814443602986151345233136170388603746969296411646714158233418888611277576374237710204734229716394950713361265013458346462648487382316305877942127752214474859094795859454295294490880154326380500685914654596927550241665243599892940472157748432105831205326132442653659482947911799058715375236555903827420335782334212566356002880715361572706447898027515949713485430213701388248011598192532689
bs = [(0, random.getrandbits(10)) if random.getrandbits(1) else (1, random.getrandbits(10)) for _ in range(2048)]
_ps = ['_' for _ in range(1024)]
_qs = ['_' for _ in range(1024)]
for i, (id, b) in enumerate(bs):
v = str((t>>i) & 1)
if id == 0:
_ps[b] = v
else:
_qs[b] = v
p_bits = "".join(_ps)[::-1]
q_bits = "".join(_qs)[::-1]
p, q = factor_bfs(n, p_bits, q_bits)
print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))
def test_3():
# Shibs - mapnaCTF 2024
n = 20316898932195904153277570911129808751568815578115203862825426326247688399447840960418077345063791379522152467572219078649052797300815169624324245983590614914067269781160218800744443132820786495383622657350005442865119235171347222481549171383138463856866590153226706585323109487068718209302113471433380661465050751463957327192775767168671487596946840993911799696944069759277414133632444513772210700794949276020219498655982617016744321984479076362225276288530893635176013522707993482886351558163399233902562390621254309853983712254751850630385079750216639722676398376824903099579116864460998259826947136455660974737633
dna = 112981924875557500958025001180130494828271302148393893025039250618449754880107262891213034570290994460680732065864408219699255537220809236513831561599199136870056419874815435027857448315805793914961273026882116413167515833581245087132919209478091324962372324771986076010340277554904109601589334046901209670673
c = 3045339581292945711130813005351003100918522557110757541588006962379795819964889960982006172396478992403763951169397699477604011489683403206194674478676115307579754281253958928474112104087602753563505848223560038859380782692201785087834133116953880301903767021262497807797262966215767967235011554145888668721199447563741572273525508047234141844260401652933196055533764562153454963082569500478073362290691632890264262315099050876574517869170470080069161301450816555901477760392115210762498464643598219802952797283932722013302922244300834587051779128033516492433437534261890143822056118794447406885925957834712258842422
e = 65537
s = 99
p_str = ['_' for _ in range(1024)]
q_str = ['_' for _ in range(1024)]
for i, b in enumerate(f"{dna:01024b}"):
if b == '1':
p_str[i] = '1'
q_str[i] = '1'
p_str[(i + s) % 1024] = '1'
q_str[(i - s) % 1024] = '1'
for i, b in enumerate(f"{dna:01024b}"):
if b == '0':
if q_str[i] == '1':
p_str[i] = '0'
q_str[(i - s) % 1024] = '0'
if p_str[i] == '1':
q_str[i] = '0'
p_str[(i + s) % 1024] = '0'
p_bits = "".join(p_str)
q_bits = "".join(q_str)
p, q = factor_bfs(n, p_bits, q_bits)
print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))
def test_4():
# this_is_rsa - seccon 2020
n = 13234306273608973531555502334446720401597326792644624514228362685813698571322410829494757436628326246629203126562441757712029708148508660279739210512110734001019285095467352938553972438629039005820507697493315650840705745518918873979766056584458077636454673830866061550714002346318865318536544606580475852690351622415519854730947773248376978689711597597169469401661488756669849772658771813742926651925442468141895198767553183304485662688033274567173210826233405235701905642383704395846192587563843422713499468379304400363773291993404144432403315463931374682824546730098380872658106314368520370995385913965019067624762624652495458399359096083188938802975032297056646831904294336374652136926975731836556951432035301855715375295216481079863945383657
p_bits = '0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____'
q_bits = '0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____0011____'
p, q = factor_bfs(n, p_bits, q_bits)
c = 9094564357254217771457579638296343398667095069849711922513911147179424647045593821415928967849073271368133854458732106409023539482401316282328817488781771665657515880026432487444729168909088425021111879152492812216384426360971681055941907554538267523250780508925995498013624610554177330113234686073838491261974164065812534037687990653834520243512128393881497418722817552604416319729143988970277812550536939775865310487081108925130229024749287074763499871216498398695877450736179371920963283041212502898938555288461797406895266037211533065670904218278235604002573401193114111627382958428536968266964975362791704067660270952933411608299947663325963289383426020609754934510085150774508301734516652467839087341415815719569669955613063226205647580528
e = 65537
print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))
def test_5():
# regulus_calendula - hsctf 8
n = 1070967922573882179692417367760420248456309713636439677513784737168798065507455125054690578149877073001572069002425729373797930733547750551400937636148971182969016272792822140103164779636336219915058989702373595895562942798667787668311267634837988264341819013654747333733422170781760297381018182461433787586377152297670011962997360422616868800134658314712129513816494813763728585344076962461314551325853100195636469366749177012032772638158979073276461027166349205437288667713822553000765151973215112878105194608990688155578357437031358928188020980709430856641483258154513163581590236992179566092627029173654407478509082715970006577586099880672105727945701894441148354173020461062571220683791863288555411212394785676166615770790140949436014247954539177005137973703301608916876584966511877310482533373226365431511627119790635073627503926678816724220796141762057169550724772373260930363251813701900759329341333531480079995245106812127214375255520736882666539315413158223865784187826023921267843052297763651750750998641156388010350564473894879259529320746217208168754737990729258083314644682404982670770719331558659278463113066604944478085594684477803558559057716120122505611554338015548743871605602897574909935805177978608484648849579290221331608525746268227952052491351881682216549911805395119521348576611612242957486024975838562356647211156701908471749066099784735037587125508000077791759300952028930521248611865850443269734966662959614699445203941262204478440284578704176140100488375118917022510842969011570034924994598944592282314072863144333881651667437771181400406696057247573300264473239471837968966933011326742847590569021782619315035004899172425231074650455325502292266363693271341991380569863082490337686939056852367733798934354875215559899176583714615894369269329066683103208700882183848411072258552050466775118099722028575925215126083599297620878410897166191888806279331534471667213799162520410842273037948001529457572610445124074038426102939195951155838983607256758051787060617914924480049209211140045443710546124169800114641091804253566275878540582924332711936871786315983506979248233452900949798324272682449237687499274489363136798687207921945618867721123863075792221617629300446229261314425919564680175902354644992995227367034699542386920884784163877250187632436523687933553247252679763219316814361385525316113378672425093325811232360647196987087279305325674321368522492688274835478928742344800906113203667514697084403775196451487973527172203783497673107
p_bits = '1111101110011000110010010___0___0___0___11010___0___0___10100___1111100111000___11011101101111100___101011010___110011010___10110___0___111110100___0___0___0___0___0___110010000___10101001110011011010111011110___0___10010___101110010___11000___0___11110___10000___0___0___1010100011001101111111110___11100___1011101010010___0___0___0___0___10010___10010___0___0___0___11110___0___10100___1011100111000___11000___100110010___0___11111110101010110___0___0___0___0___11010___0___10010___11010___11110___1100111110100___0___0___1010111110010___0___0___11000___10100___0___11000___0___101111100___0___0___0___0___10010___0___0___0___0___0___10110___10100___1000110110000___1001111011110___11110___0___11110___10100___110110100___10100___0___0___111111111010101011110___101110000___0___0___10111101101011110___0___100011011100111010000___0___11100___0___0___0___0___1101101110100___0___0___0___0___0___11011110100010000___0___10010___0___10000___0___1111100011001011100110010___11110___0___0___0___0___0___0___0___0___101110000___0___10000___11110___11010___0___0___111011100___0___11010___0___0___111110000___0___1111101011010___1000111010010___10010___0___0___0___10010___0___0___0___0___10010___1110110010000___0___0___101111010___101011110___0___10011101101010010___11010___11110___0___111110110___0___10100___0___10000___11000___111111110___10000___0___0___0___0___10000___11000___0___11010___0___0___11000___10110___0___11001110111011100___0___10110___111111100___10010___0___10011101101111010___10010___1100111010010___0___0___10010___10100___0___0___0___100011010___0___0___0___11001101110110001001111010010___11010___0___0___101110100___0___0___11100___111111001000101011000___11100___0___0___0___0___0___11000___0___0___0___0___101110010___0___0___111111110___101011001011110111111011100111000___110010010___0___10010___0___0___11010___0___0___0___111111010___10110___0___0___0___11010___0___0___1101100010010___0___0___0___0___100111111100100110110___0___100111100___0___110111110___11100___0___0___111011110___0___111010110___10110___10110___10011101110011100___11010___100111110___0___0___1010110010110___1000100011110___0___110011110___0___0___10010___11111110110011110___0___0___0___100110010___110111110___0___10010___11110___1101101111100___1110101011100___100110000___0___0___0___100110110___0___10000___0___110111000___100011110___0___0___0___10111010110010110___0___0___110010000___0___0___0___10010___0___0___1110101111111000101111010___11010___0___1000101011000___1101100111110___0___0___1001101110010___0___1000101110100___1111101110110___0___0___0___0___0___0___0___0___110110110___10000___10010___0___0___0___111010000___10010___0___110111111000110011100___0___0___10000___0___110011110___1110111110000___0___11010___11110___0___0___0___11110___0___0___0___1100110010000___11110___11000___1010111111010___11100___10000___0___11010___1111111011110___0___0___0___101011100___0___101011000___111110000___0___0___0___1010110010110___10001011110011110___11110___0___0___0___0___11101111101111110___0___11010___0___0___0___110011110___11100___0___10000___11000___100011101011110110011011111110001110101111100___11110___10010___0___10110___11000___111011110___10010___1000100111010___11010___0___11110___0___0___0___1110110110110___0___101111100___0___11100___0___10100___10010___0___0___10110___0___111111110___100010000___0___1101100110010___10010___10001000110011000___11111000110010110___0___1000111010100___11100___10110___10110___11110___0___1010111111110___0___11110___0___0___101111000___0___10010___0___110111110___10100___10000___0___111011111011110011000___0___0___101111011101100010010___11010___0___0___111011110___11100___0___11000___110011010___1010101111110___11000___0___0___10000___10100___0___0___11100___100011010___0___10110___0___11010___10100___0___10000___0___10010___1010100011000___101111000___11000___0___1101111111110___0___101010101101111110000___0___0___110010100___0___0___111110000___0___0___0___101011110___0___0___110011110___10110___0___0___0___10110___1001101010010___10100___101011010___0___101110100___0___11000___10010___10000___0___11010___1011'
q_bits = '1111111111000___101011010___0___110011100___0___110111000___100111101001101010110___0___10000___0___0___101110000___0___0___0___11010___110111110___0___11110___10011011111110100___0___10000___0___0___10100___0___0___10110___0___101010000___0___0___100110110___100111110___0___101111100___0___0___110010110___111011010___0___0___11111001101111010___110010100___0___111011110___0___0___0___0___111010100___110010001010110111000___11100___0___0___1011100010000___11111011111011111100101111001100111111001111100111110___11111011110110000___0___0___110011110___10110___0___0___0___11000___0___110010000___10010___110111000___111011000___0___0___0___0___0___10110___10010___111011010___11110___11001000111011000___0___0___10110___101111100___10100___11000___10000___0___0___10110___0___111110100___10000___10110___11101010110011010___0___0___10001111110110100___0___10100___0___0___10110___111010100___0___0___10110___0___0___1000111110100___0___0___11100___101010000___0___0___11010___0___11010___10000___1100100110101111100111110___0___0___0___11000___10000___10100___10100___0___0___111110010___10000___10011010111110010___1010111111000___0___10110___10000___0___0___0___100010100___10000___0___11110___0___0___0___0___0___0___100110110___10010___0___0___0___11011011111110010___11110___0___0___0___1011100111110___111110010___100011000___0___0___1000110110010___1111101110100___0___0___11100___101010000___0___10110___0___11011111101111011111110110000___10100___0___0___11010___0___10100___11100___110010111010110010010___0___100011010___11110___1100111011011011101010000___0___0___0___0___10010___0___10100___10010___101011100___1100101010000___0___0___0___11100___0___10110___11010___10100___0___0___111010100___0___11100___11100___10000___0___110010110___0___0___0___0___0___0___10000___100011010___100111100___11110___0___1100111010010___0___10110___0___0___10100___11001101111011100___0___0___10010___0___0___11010___10100___0___1110100011110___0___11110___0___0___0___0___0___0___0___0___0___0___0___0___0___0___0___10101111100011100___0___11100___0___0___0___0___0___100110110___1101101110110___0___11110___10000___101011010___0___1110111111100___0___11110___111011010___100110010___101111010___0___0___1010111111111001111110110___0___11000___11010___0___11011010101110100___0___0___10100___10100___0___10000___0___0___10110___10010___0___0___0___0___11110___100111000___0___1100110111110___11010___0___11010___0___0___0___11110___0___0___10110___0___0___0___0___0___0___0___100010110___100011001001100110100___0___0___10000___0___0___0___110110000___10000___0___111111000___0___10011111110111010___100111110___0___0___0___110010000___101110100___111110100___1010111111100___0___0___110011100___0___11101111111110110___10010___10000___111110101010111110110___0___0___100011100___100010010___1101101111101101111011111000111111110___0___1101110011010___1011100011111101111011000___0___0___111111001111100010000___0___1010100010000___0___11100___0___10110___0___0___0___0___0___0___10100___0___100011010___10000___111011001010111011011010110010000___0___110011110___11100___11101100111010010___0___11100___111010010___0___11100___0___0___10100___0___111110110___0___11101110100110100___0___0___0___0___0___10110___0___1011101011110___111011100___111110010___0___0___0___11001100111011000___10010___0___100010000___0___0___11100___0___1110111010110___10110___10100___10110___0___0___0___10100___11110___10010___11100___111110010___101111100___0___10110___0___0___0___0___0___100010010___0___11110___0___101010000___0___0___101011110___111011110___100111000___0___0___10110___0___0___0___0___10110___0___0___1010101011101100100110101001110111000___101111000___101010100___0___0___0___10110___11110___10000___111111010___0___10010___10100___11100___0___11111001110011100___10011111110110111011101110000___10000___10110___10100___0___100110110___0___0___0___11000___0___0___11000___0___0___10100___101011100___111110100___11100___11100___0___111111000___0___110010010___0___0___0___10010___0___0___1001100111111111110011110___0___10100___0___101111100___111110010___11010___0___0___0___101010011001'
p, q = factor_bfs(n, p_bits, q_bits)
e = 0x10001
c = 143246098704050838246084126891490277226903552802940512915424080544776324845181609769441267172096344119910338915209870531033571558702590728936571042903055093876639697317207462513677207308160129408431098752681365224006093669674530149275914823552496143933723556044461406543124286154973048772770561345970817283157532690733440131806801047663791015321028485337721116836129352509400796086816706637519310813407251978620892383479125150351564945498042054104436617752412742236106859139168679601530620673023201110807487298469858013590439937536503070190172774315217979748580601010289688998891270751561549625395303533578216358161484716324880572832284109120640920482137061167742017194469223967633212137110296659877534225167234476554434032622977786880123650200443441387237183067276246002550441256572029570426034588193265350701255821656856981676822719981674462066016447016217272786049188187555512810152526323216269952573674816754418056579381927178884071984392810753862715074473888037904917387908476767944799065298165474365136397738973662951759389479314176429974034168748125322274525911820538823731796077256875166632342401806229298347515233050303534948179416096269770382077798843111764374818258811487961561217421629203632908939677163173597713283580544599858395650575469712917392305443271840187847610834966263386739325391914147021896109821942345709931345235500749332896338794507778099412554939685378349826860227472589683322486926920551319602047182846025838937692071411402848675185032818511746106991565033651374420605946142823675320882775141709527111106945141354791941083105705681536876782637082275204200069575942603464380903316500016095295488960702636222535073358563239682363807609348335540576660328726982399013082911572012826555537998232014644385184058082572752171502422792719993533042741100166743384313662562465500363037373597364249749629279546483186498466528119331961002316830636539529036671104373297278707457198589304407721519010717116262481169050580564357388073765954404879899984220872561956143803583133988311240742030583374132676705030523332599501807188984120599365037198441326996736259422318819500626080967225403270894284495696523070932543625806785051971012847210305339348777034038783453797360705144197733640106552963065914840583296717711465289034468334039170251394430388077478480124296003475687982374403971025176602614566870624279015234133701242347065784995657931035004959276502700565334164586624163248129845689189390070829734871056551504164558098140817029364355224811296667542
print(long_to_bytes(pow(c, pow(e, -1, (p-1)*(q-1)), n)))
def test_6():
from Crypto.Util.number import getPrime
import random
p = getPrime(1024)
q = getPrime(1024)
n = p*q
prob = 55
p_bits = "".join([i if random.randint(0, 100) < prob else '_' for i in f"{p:01024b}"])
q_bits = "".join([i if random.randint(0, 100) < prob else '_' for i in f"{q:01024b}"])
print(factor_bfs(n, p_bits, q_bits) == (p, q))
test_1()
print()
test_2()
print()
test_3()
print()
test_4()
print()
test_5()
print()
test_6()