RSA2048 smallest possible modulus
$begingroup$
what is the smallest possible modulus for RSA2048? I generate a random data with I want to encrypt by a textbook RSA2048 and I'm not sure where the first 1-bit should be.
According to OpenSSL source code and used padding function, the first byte seems to be 0, 2 follows and than there could be anything. Seems I need first 14bits to be 0 to ensure my plaintext fits the RSA modulus.
rsa
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
$endgroup$
add a comment |
$begingroup$
what is the smallest possible modulus for RSA2048? I generate a random data with I want to encrypt by a textbook RSA2048 and I'm not sure where the first 1-bit should be.
According to OpenSSL source code and used padding function, the first byte seems to be 0, 2 follows and than there could be anything. Seems I need first 14bits to be 0 to ensure my plaintext fits the RSA modulus.
rsa
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
$endgroup$
1
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
1
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04
add a comment |
$begingroup$
what is the smallest possible modulus for RSA2048? I generate a random data with I want to encrypt by a textbook RSA2048 and I'm not sure where the first 1-bit should be.
According to OpenSSL source code and used padding function, the first byte seems to be 0, 2 follows and than there could be anything. Seems I need first 14bits to be 0 to ensure my plaintext fits the RSA modulus.
rsa
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
$endgroup$
what is the smallest possible modulus for RSA2048? I generate a random data with I want to encrypt by a textbook RSA2048 and I'm not sure where the first 1-bit should be.
According to OpenSSL source code and used padding function, the first byte seems to be 0, 2 follows and than there could be anything. Seems I need first 14bits to be 0 to ensure my plaintext fits the RSA modulus.
rsa
rsa
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
edited Dec 31 '18 at 21:28
Ella Rose♦
17.1k44586
17.1k44586
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
asked Dec 31 '18 at 13:42
smrt28smrt28
53549
53549
1
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
1
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04
add a comment |
1
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
1
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04
1
1
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
1
1
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).
But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
$endgroup$
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66198%2frsa2048-smallest-possible-modulus%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).
But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
$endgroup$
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
add a comment |
$begingroup$
The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).
But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
$endgroup$
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
add a comment |
$begingroup$
The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).
But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
$endgroup$
The modulus defines the key length for RSA. So a 2048 bit key has a 1 at the leftmost bit. Otherwise there could be almost any number of zero's following it, each zero becoming less likely, as the modulus value depends on two large random primes - usually in the order of half the bit size of the modulus. So if you want to take a minimum modulus $N$ into account, you can have any 2047 bit message for plaintext RSA - as long as the most significant bit of the most significant byte is zero (commonly RSA uses big endian calculations, so that would be the highest order bit of the leftmost byte).
But please note that plaintext RSA is insecure; the security of the scheme would depend on the content of the message. If it by chance is a fully OAEP padded message then it is certainly secure if verified correctly, but I'm not sure you would implement a secure scheme by chance. Actually, I would consider it highly unlikely that a scheme would survive even the simplest of plaintext oracle attacks.
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
answered Dec 31 '18 at 14:22
Maarten Bodewes♦Maarten Bodewes
56.2k679197
56.2k679197
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
add a comment |
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
The idea is to generate longest possible ciphertext from password by PBKF2, use Yubikey to decrypt the random-like data, and use another PBKF2 from those "decrypted" data as a key for LUKS disk encryption.
$endgroup$
– smrt28
Dec 31 '18 at 14:29
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
$begingroup$
...the idea is to protect the LUKS crypto-key by the PIN. This would be a workaround, since I haven't found any way how to store arbitrary data on Yubikey protected by PIN.
$endgroup$
– smrt28
Dec 31 '18 at 14:32
1
1
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
$begingroup$
That sounds as properly randomized data. However, I don't see any reason to store more than the output of the hash size. In that case you can still wrap it in a secure scheme such as OAEP. Storing more than the hash size for PBKDF2 actually could shift the advantage to an adversary - although if you feed it directly into another KDF I guess that's not as likely to happen. Still, outputting more than a single hash doesn't make PBKDF2 any more secure; the hash size is still the limiting factor.
$endgroup$
– Maarten Bodewes♦
Dec 31 '18 at 15:18
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66198%2frsa2048-smallest-possible-modulus%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
what you mean by smallest module? See this:
$endgroup$
– kelalaka
Dec 31 '18 at 13:51
$begingroup$
c^e mod m. The m is module/modulus?
$endgroup$
– smrt28
Dec 31 '18 at 13:53
1
$begingroup$
What is the reason other than curiosity? do you need to find $n=pq$ where two $p$ and $q$ are two primes such that $n$ is the smallest possible 2048-bit integer?
$endgroup$
– kelalaka
Dec 31 '18 at 13:56
$begingroup$
No, the RSA2048 key is just a common OpenSSL generated key. I need to generate c that way I can be sure c < m and can be used as a plaintext RSA2048 input in general.
$endgroup$
– smrt28
Dec 31 '18 at 14:02
$begingroup$
For text book RSA every $m in mathbb{Z}_n$ is valid. For padded RSA see the link that I provided in the first comment.
$endgroup$
– kelalaka
Dec 31 '18 at 14:04