<jupyter_start><jupyter_text>The reblocking problemSuppose that Alice wants to send Bob a signed and encrypted message $m$. She will use RSA for both signing and encrypting. She first uses her private key $(n_A, d_A)$ to obtain the signature $s = m^{d_A} \bmod{n_A}$, and then uses Bob's public key $(n_B, e_B)$ to obtain the ciphertext $c = s^{e_B} \bmod{n_B}$. She sends $c$ to Bob, who then decrypts it with his private key $(n_B, d_B)$ to obtain $s' = c^{d_B} \bmod{n_B}$, and finally recovers the message $m' = s'^{e_A} \bmod{n_A}$ using Alice’s public key $(n_A, e_A)$.<jupyter_code>nA = 62894113
eA = 3
dA = 41918819

nB = 55465219
eB = 17
dB = 26094257

m = 2<jupyter_output><empty_output><jupyter_text>Let us first sign the message $m$ with Alice's private key, and then encrypt the signature using Bob's public key.<jupyter_code>s = Integer(pow(m, dA, nA))
s
c = Integer(pow(s, eB, nB))
c<jupyter_output><empty_output><jupyter_text>We now decrypt the ciphertext using Bob's private key, and then extract the message with Alice's public key.<jupyter_code>ss = Integer(pow(c, dB, nB))
ss
mm = Integer(pow(ss, eA, nA))
mm<jupyter_output><empty_output><jupyter_text>Let us try with another message.<jupyter_code>m = 5
s = Integer(pow(m, dA, nA))
c = Integer(pow(s, eB, nB))
ss = Integer(pow(c, dB, nB))
mm = Integer(pow(ss, eA, nA))
(m, s, c, ss, mm)<jupyter_output><empty_output><jupyter_text>We se that since the original signature $s$ was larger than Bob's modulus $n_B$, decrypting $c$ only gives $s' = s \bmod{n_B}$, leading to $m' \ne m$.The probability of this happening can be expressed as $(n_A - n_B)/n_A$, where $n_A > n_B$. Let us compute it for our case.<jupyter_code>N((nA - nB)/nA)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1351039260969977, 'fraction_numerical': 0.021362586605080832, 'mean_word_length': 5.324817518248175, 'pattern_counts': {'":': 0, '<': 21, '<?xml version=': 0, '>': 22, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '388926', 'license': 'MIT', 'n_tokens_mistral': 719, 'n_tokens_neox': 669, 'n_words': 228, 'path': 'notebooks/ReblockingProblem.ipynb', 'repo_name': 'tp4348/kirv', 'size': '1732'}