Tag Info

New answers tagged

0

Using a bignum library such as OpenSSL, you can calculate everything very easily. Create a new RSA structure using RSA_new(). Convert the hex strings to BIGNUMs using BN_hex2bn(), storing them in rsa->p, rsa->q and rsa->e. Calculate p-1 and q-1 into temporary variables using BN_copy() and BN_sub_word(). Multiply those two into a third temporary variable ...


0

Look up the OpenPGP secret key format (some kind of ASN.1 I think?). Use your favourite bignum implementation to multiply p by q and store this as the modulus n (in the correct format). To calculate the decryption exponent, you need $d$ such that $ed=1 \pmod{(p-1)(q-1)}$. This can be found with the extended Euclidean algorithm (the wikipedia pages for RSA ...


0

I think your key doesn't work, because it is only a signature key. That's subpacket 27, for which pgpdump says: Hashed Sub: key flags(sub 27)(1 bytes) Flag - This key may be used to certify other keys Flag - This key may be used to sign data The corresponding output of gpg -vv mykey.pub is :signature packet: algo 1, keyid ...


-3

I am answering this in the context of Digital Signatures. Digital Signatures offer - Authenticity (that the message was sent by the person whom the message claims to be sent by) and Data Integrity (that the message was not altered in transit). Suppose, you encrypt the entire message using private key and send it out. Now, any body will be able to decrypt ...


2

Usually the public exponent is first chosen. Often it is the 4th prime of Fermat (e.g. -f4 for openssl), 65537. This number in binary is: 0000 0000 0000 0000 0001 0000 0000 0000 0001 Fermat primes are primes with just 2 bits set. 3, 5, 17, 257 and 65537 are the only known Fermat primes. It is relatively easy to use this as exponent as only two bits are ...


1

The fastest way to solve your problem instance is as outlined in the above comments. First choose yourself a random message $m$ with $1<m<n-1$. Now compute $c\equiv m^d \pmod n$. Try if any of the following equations holds, if an equation does hold you've found the public exponent $e$. $m \equiv c^3 \pmod n$ $m \equiv c^{17} \pmod n$ $m \equiv ...


2

The first (and hardest) step is to factor $n$; the easiest way to do this (given $e$ and $d$) is with this randomized procedure: Select a random value $z$ from the range $(2, n-2)$ Compute the value $\lambda = (ed-1)/2^k$, where $k$ is that integer that makes $\lambda$ an odd integer. Compute $t = z^\lambda \bmod n$. If $t = 1$ or $t = n-1$, we fail on ...


0

Without knowing the exact implementation you are using, from the algorithm name, I think you are generating a random key for the symmetric cipher and encrypting that with the RSA key. This way your ciphertexts will be unique. I would recommend using a cipher mode that provides integrity protection, such as AES-GCM or Poly1305-AES. ECB could be dangerous if ...


10

The premise "we don't have a way of generating and verifying a 2048-bit prime number with 100% accuracy" is wrong (if we trust the computers performing the operations): it has long been known practicable ways to generate randomly-seeded provable primes, and it is a (somewhat marginal) practice in RSA key generation (see FIPS 186-4 appendix B.3.2). We can ...


1

I don't think this problem is solvable as specified. With a small message space, and deterministic hashing (or encryption), a generic attack involves exhaustively searching all likely messages to find one that corresponds to the known hash / ciphertext. If all of the digits of the ID numbers were random, an exhaustive search would require about $10^{10} ...


0

We do use the secret key to sign the message as otherwise anybody would be able to sign messages (in your name!) You can hash a message by passing it to cryptographically secure hash function, like SHA-2/3 and interpret the resulting digest as integer $m$. The verification (of plain RSA, please note: RSA is never deployed like this) of RSA-signatures ...


1

The client generates a random symmetric key and encrypts it with the public key. This public key needs to be trusted. Make sure you use a good padding mode, OAEP should do it. Send to server, server decrypts it with the private key. Eh, that's it. No forward security though, the session can be decrypted if the RSA scheme is broken or if the private key is ...


3

If you can efficiently find a $P$ that is not coprime to $N$, then you can easily factor $N$ (use GCD). If you know the factorization of $N$ (say $N=pq$), you can easily find a $P$ that is not coprime to $N$ ($kp$ for some constant $k$). This established the fact that finding $P$ not coprime to $N$ and factoring are equivalent problems. Now, how many ...


4

You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$. In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell ...


2

Your calculation is broken. First as pointed out correctly the expected run-time of GNFS (general number field sieve) is: $O(exp((\sqrt[3]{\frac{64}9}+o(1))*\sqrt[3]{ln(n)}*\sqrt[3]{ln(ln(n))}^2))$. So next you can't just set these $O$s equal, as $O(f(x))$ means $O(f(x))< k*f(x)$ which means this is an asymptotic upper bound meaning you need some ...


0

The standard definition of RSA (PKCS#1) has two formats for a private key corresponding to public key $(n,e)$ with $n=p\;q$ where $p$ and $q$ are distinct odd primes: $(n,d)$ where $e\;d\equiv 1\pmod{\operatorname{lcm}(p-1,q-1)}$ and $0<d<n$, from which it follows there are at least two private keys in this format; $(p,q,dp,dq,qInv)$ where ...


1

You cannot, you can however create a hash over the modulus. This is sometimes used as identifier for a key pair, e.g. in PKCS#11. The modulus is unique for RSA key pairs.


1

You can't. Recovering the md5sum of the private key means uncovering the private key, which is considered impossible for large values of $n$.


1

If I'm understanding your question right, you want to obtain $d$ from given $n$ and $e$. You'll have to factor $n=33=3*11$ and as $N=p*q$ you have obtained your $p=11$ and $q=3$. Now proceed as usual with calculating the inverse. As pointed out correctly above, you can't easily generalize this approach to larger numbers as factoring $n$ will be infeasible. ...


1

The standard algorithm used for RSA encryption and decryption is exponentiation by squaring. The basic idea is to write the exponent out in binary. For example, for $d = 4267793$, $$\begin{aligned} 4267793 &= 10000010001111100010001_2 \\ &= 2^{22} + 2^{16} + 2^{12} + 2^{11} + 2^{10} + 2^9 + 2^8 + 2^4 + 2^0.\end{aligned}$$ Now, given some RSA ...


0

Mathematically, yes, it will work. Practically, you will require an extremely very long time and an incredible amount of energy, considering the sizes of the primes involved in RSA (usually around 1024-bit prime numbers). It is about billion and billions of years and billions and billions times the energy of the whole universe (RSA: How effective is this ...


2

If you know a multiple of $p$ and $k$ is smaller than $\sqrt(p)$ than you can use a different approach than the one by poncho. Note: knowing a multiple of $p$ is the typical case of RSA where you know the modulus $N$ made by $p\times q$, so if your question refers to RSA you are left only with the constrain on the size of $k$. The method you can use is an ...


4

If $p$ is prime, then $\phi(p) = p-1$; so the question is "given $k(p-1)$, can someone get a good guess of what $p$ might be?" It is unlikely that the attacker would be able to limit it to one particular value of $p$ (as there are likely to be multiple values of $p$ that are plausible), however the attacker might be able to construct a short list of ...


2

RFC 2313 specifies the RSAPrivateKey ASN1 structure as a SEQUENCE containing the INTEGERs $0$; $n$; $e$; $d$; $p$; $q$; $d\bmod(p-1)$; $d\bmod(q-1)$; $q^{-1}\bmod p$. The PEM format consists of such a structure encoded as Base64 and framed by the typical BEGIN/END RSA PRIVATE KEY header and footer lines. Thus, you can use any ASN1 library you like to ...


0

"We are using ECB with RSA": It's difficult to understand what you mean by this; nobody does it, ever, so we have no "default meaning" to fall back on. You will have to describe your protocol in more detail, and then we can tell you why it is flawed.


5

It is highly misleading to call how RSA Encryption is used as 'ECB mode'. With ECB mode, we break the plaintext into N bit segments, and send each one through the block cipher separately. The block cipher is deterministic, and so if two plaintext blocks happen to be the same, so will the corresponding ciphertext blocks. Now, with RSA encryption, we take ...



Top 50 recent answers are included