Hot answers tagged

17

Yes. The McEliece cryptosystem using Binary Goppa codes has withstood cryptanalysis to date. Its hardness is based on decoding. I should note that it has been broken for certain classes of codes. Another common example is the Merkle-Hellman knapsack cryptosystem. Unfortunately it was broken. It is likely possible to build a secure cryptosystem based on the ...


11

In addition to McEliece (already mentioned by Mike), there's also Hash Based Signatures (such as this one); these are signature algorithms that is based only on some security assumptions of a hash function (and typical hash functions as about as far from numeric-theoretical problems as you can get)


9

This is not correct, the private key $d_A$ must always be an integer. Your mistake is that you are doing modular division e.g. $\frac{a}{b} \text{ mod } n$ incorrectly. You cannot simply divide the integers and then reduce by the modulus. The correct way to do this is to compute the modular inverse of $b$ i.e. $b^{-1} \text{ mod } n$ and then compute $a*b^{-...


8

What does DH add? Perfect Forward Secrecy. That is, suppose you have a secure session with the server Bob, and then you close the session down. Then, someone steals the server (or serves a warrant to the owner). If you use RSA to transport the random session key, well, the server still has the RSA private key, and so they'll be able to decrypt your ...


6

Can exponent be random number just like it is now or it should be a prime too? There is no particular advantage to be gained in selecting only prime exponents. Is using dynamic modulus and generator better idea? Whether it makes sense to use dynamic modulii is currently under debate. There are known algorithms that make attacking multiple discrete ...


6

When choosing the public exponent $e$, if the value chosen is the first coprime after $\phi(n)/2$ then the resulting public and private exponents are equal. Well, yeah, that'll always be true. Why does this happen? We have $e=d$ whenever we have both of the following true: $$e^2 \equiv 1 \pmod{p-1}$$ $$e^2 \equiv 1 \pmod{q-1}$$ Now, if $e = (...


5

BitTorrent, when encryption is used (optional in most clients), uses the Diffie-Hellman protocol for key exchange and RC4 for confidentiality. It also drops the first 1kb of data from the RC4 output as part of the specification. There is no authentication, not really enforceable anyway due to the nature of peer-to-peer sharing networks. Standard theory ...


4

Another solution (cf to @Raoul722 comment) is the following: It is easily feasible with a mix of symmetric and asymmetric encryption. Assume each user $k$ have a key pair: $(K_{pub}^k,K_{priv}^k)$. The admin also have his key pair: $(K_{pub}^{admin},K_{priv}^{admin})$ where $K_{pub}^{admin}$ is known by all. Encryption scheme for a user $k$: generate a ...


4

OK, so this takes a bit of guessing, but I'm assuming the following: A is the identity of A, which can be used to select the right public key of A; Kxa() is a signing operation (with message recovery) that signs the random Ra and a tag Ts which is used as proof; Kya() is an encryption operation with the public key A, so that the session key Ks is kept ...


4

There are known impossibility results regarding basis public-key cryptography on NP-complete problems. In this paper by Goldreich and Goldwasser they show that under common types of reductions, it is not possible to base public-key cryptography on NP-hardness.


3

This is only useful as a thought exercise, but Alice and Bob can do key exchange based only on the strength of AES or some other private cipher: Assumptions: doing $2^{40}$ operations will take "a while" but is doable; $2^{80}$ operations is out of the realm of possibility in a century. Alice can publish arbritary amounts of information which cannot be ...


2

The OpenPGP message you posted is a signature, not a key. As it was issued by GnuPG, I assume you're using GnuPG anyway. To export your public key, run gpg --armor --export [key-id]. --armor wraps the output in a base64-like encoding (like the signature block you provided in your question), otherwise you'll get binary output. If you don't know your key-id, ...


2

I was in your shoes about a year ago. The biggest help to me was Kahn Academy's crypto lessons (https://www.khanacademy.org/computing/computer-science/cryptography). The best thing it did for me was to define what many of the terms were without going too deep into the math. To directly answer your question, the most basic cipher is letter substitution: A = ...


2

Here is the solution to M^e is less than N: http://asecuritysite.com/encryption/crackrsa2 An alternative method is here as a fun article: http://asecuritysite.com/encryption/crackrsa5 Do you have the Cipher value?


2

First use the TID as input for a KDF to generate one or more tag specific keys, using a static, symmetric master key stored in the initialization software and gadget. Use one of these keys to obtain access. Use another for verification of the tag. During initialization derive and set the access key (s). Then create a HMAC over a static value (or multiple ...


2

Let's assume that T does send A,Kxt(Ra,Ts) to B as you have indicated. In that case upon reception and validating the signature, B would immediately be able to tell that the signature does not belong to A (and should thus not continue the exchange). To try to take advantage of the exchange, T would have to alter the message from A so that it still looks ...


1

I am currently looking at “A SAT-based Public Key Cryptography Scheme” (PDF) where it is proposed a Public Key Cryptography Scheme based in Boolean Satisfiability Problem which is NP-complete. It seems pretty interesting and the autor also provides an implementation at GitHub. The public key is a SAT formula satisfied by the private key.


1

Let $c_a$ be the encrypted version of $a$, and $c_b$ be the encrypted version of $b$. What you want to compute is $c_c$ which is the encrypted version of $a-b$, so that when you decrypt $c_c$ you get $c=a-b$. Paillier supports a homomomorphic addtion of ciphertexts to get an encrypted version of the sum. The actual mathematical operation it takes to get ...


1

What you're missing is the fact that your $c$ value can get waaay beyond what the library is expecting there and thus issues an error which can be read as "your value is too large". The solution is simple: Reduce the multiplication result $\bmod N^2$, where $N=pq$ is the actual value of your modulus. The code-line which you would need to add there would ...


1

No, there is no checksum built-in to the RSA keys per se. There is no need for that. Does this breaks the key ? Or changes the key internally, without breaking it ? [EDIT] It was rightfully pointed out to me that at least one of the statements I typed (in haste) was plain wrong. Now that the answer has served its initial purpose, I've removed my ...


1

As fgrieu noted in his answer using sign-then-encrypt is probably the best way of handling encrypted & signed messages. However when the OpenPGP format in RFC 4880 is studied it seems that it uses both PKCS#1 v1.5 padding and CBC mode encryption. Both schemes are vulnerable to padding oracle attacks. So it is important to make sure the software is not ...


1

Yes, PGP's sketch as in the question is sound by today's textbooks on cryptography, and reasonable from a computer security standpoint. Applying digital signature then encryption (critically: including on the signature) does provide data integrity and confidentiality for the message. PGP's way of doing things has the characteristic that one able to decipher ...


1

Yes OpenSSH's fingerprint is a hash of the publickey, and (except SSHv1 keys aka -t RSA1 which is long broken and should never be used) specifically of the publickey format stored in base64 in (usually) /etc/ssh/ssh_host_${alg}_key.pub which is the wire encoding in the relevant KEX-reply message depending on key type (currently RSA, DSA, ECDSA, ED25519). See ...


1

It will be a bit of a journey to get to the answer for your question, but check out Khan Academy's crypto series: https://www.khanacademy.org/computing/computer-science/cryptography They do a nice job of explaining how all the maths work with pretty small numbers. Even colors, which is an awesome analogy.


1

A simple way to consider the question is: Can we factor a given 2048-bit RSA modulus $N$, assumed to be the product of two 1024-bit primes $p$ and $q$, if also given the 256 high-order bits of $p$? That class of problems is studied by Don Coppersmith: Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities, in Journal of Cryptology (...


1

I have modified this Ruby script to not require public keys and to allow direct (r,s) input. Funnily enough, I stumbled on this thread (created two hours ago as of writing) on Google searching for the exact same problem. Note that I am using Secp192r1 (due to a CTF challenge), so feel free to modify that to your likings: require 'ecdsa' msghash1_hex = '...


1

You can send the public key certificate as an attachment with the email or you can send the public key certificate in a separate email. The main point is the end-user should receive the public key for verification. A certificate can be a file e.g. *.cer . The end user needs to have a program to verify the document. UPDATE: Chances of an MIM attack or ...



Only top voted, non community-wiki answers of a minimum length are eligible