How to ethically publish the result in case we prove that P = NP? Suppose a researcher discovers that $P=NP$, and has an efficient algorithm for some common NP-Complete problem.  Given the implications for cryptography, what would be the most ethical way for them to reveal this knowledge to the world, without causing the downfall and destruction of technological civilization?

I'll try to answer what I view to be a much easier question to answer, while still (in my view) capturing the "essence" of the problem.

How can one "prove" that they have an efficient algorithm for an NP-complete problem without publishing the algorithm?

There are many things one can do, but the simplest is to solve challenges.
There are a large number of computational challenges which have been posted over the years, for example:

RSA factoring challenges

Lattice Crypto challenges

If one solved a variety of these challenges in extremely high dimension and posted the solutions publicly, it would very quickly erode confidence in the hardness of the underlying problems.
After waiting a suitable amount of time, you could then publicly post your algorithm.
Of course, it is difficult to talk about what a "suitable amount of time" is for public disclosure that would break all of cryptography, which is why I avoided your initial question.

There are algorithms to crack encryption, there are just no known algorithms to crack any half decent crypto in a reasonable amount of time.
A proof that P = NP doesn’t make such algorithms magically appear over night. And just because we now know there is a polynomial time algorithm, that doesn’t mean we are going to find one, and it most definitely doesn’t mean we can find an algorithm to break crypto in a reasonable amount of time. Breaking some crypto with an n-bit key in $n^{100}$ nanoseconds is polynomial time, but useless in practice.
PS. An efficient algorithm for SOME common NP-Complete problem X does not show that another problem Y which can be reduced in polynomial time and space to X can also be solved efficiently. For example, that reduction could take $n^{100}$ nanoseconds, and how long solving X takes is not of much interest anymore.


"Padless" One-time-Pad encryption I have just read about the perfect security of an OTP encryption and what came to my mind was that what if the Pad used for encryption/decryption did not have to be transported separately from the message, but instead together with it?

And what if it was computed using an algorithm from the message itself (from all the characters in an 1:1 way so that it had the same size) providing a random-looking pad for encrypting the message, and after encrypting the message would be stored in an interwoven way in the message itself, expanding the file size by a factor of 2. The encrypted file itself would have double size of the original one but no-one would be able to find out what is the message and what is the key since it would be interwoven using a secret algorithm, perhaps the same one as was used for generating the pad.

Would this be a good encryption comparable to real OTP with the pad transferred and generated separately? Did I just invent the wheel, or is this a breakthrough thing (I mean storing the pad inside the file in a secret way preventing others to extract it)?

I know calculating the pad from the message itself would perhaps break the real randomness so this could be avoided and the pad simply taken from a real random key number generator.

Your "secret algorithm" is now effectively the key.

If the algorithm stays fixed for all messages, you now no longer have a one-time pad. So let's make your algorithm be tweakable by, say, accepting as input a string that describes its exact operation. Now we have the benefit of being able to publicize the "secret algorithm", since the actual secret details are contained in this input string. Except now that input string is the key, and now you have to find a way to transmit it... which is the problem you were trying to solve in the first place.

You cab easily program a dice functionality. You don't necessarily have to rely on the broken random functionalities, for whatever reason, people like Bruce Schneier seem to recommend you use.

require "digest"
sha512 = Digest::SHA512.new

eDice = ["00", "01", "02", "03", "04", "05", "06", "07", "08", "09"]

512.times do
  sha512 << eDice.sample.to_s
  int = sha512.to_s
  print int.to_i
  print int.to_i
  print int.to_i
  print int.to_i
  print int.to_i
  print int.to_i
  print int.to_i
  print int.to_i
  print " "
end
puts " "

I think the better question is why "security professionals" somehow expect you to use programs written deliberately obtuse, if not blatantly not freedom respecting software.

Random enough for my purposes.


Secure encrypt-then-sign with RSA I understand that when you want to encrypt and sign data with RSA the generally recommended approach is sign-then-encrypt.

However, I have encrypted data that I need to sign, to prove the author of the encrypted data.

Encrypt wth recipient's public key
Sign with author's private key
Concatenate cipher text with signature

From reading papers such as this, it seems that the problems with sign-then-encrypt are quite subtle, but solutions are quite straightforwrd.

I haven't been able to turn up much on issues with encrypt-then-sign. I guess one problem is that someone could simply strip off the signature and replace it with their own. My first thought was to prefix the data with the author's public key before encrypting, but then the signature can only 'really' be verified by the recipient (public verification is more desirable for me).

What are the issues associated with encrypt-then-sign, and what solutions exist?

** Edit **

I thought of another potential solution to the problem of someone replacing the original signature with their own - using X.509 certificates. So in step 3 above we also concatenate the certificate of the author. When verifying the signature we check that the public key matches that of the certificate, and we also verify that the certificate was issued by a particular, trusted CA. With this scheme, not just anyone can replace the signature, only those who are issued a certificate from the trusted CA. Any issues with this approach?

The primary problem with encrypt-then-sign (signing the ciphertext) relates to the difference between signing for the purpose of assigning responsibility vs for the purpose of taking credit.  Encrypt-then-sign is OK for the former but not for the latter.  The issue is quite subtle.

In particular, in your protocol, the recipient has no reason to believe the sender (signer) was ever aware of the contents of the plaintext.  The signer must have been aware of the contents of the ciphertext and approved signing the ciphertext, but this does not mean that the signer knows or created the original message.

For instance, suppose we're using this to log into a site.  Suppose Alice, who is a system administrator, is going to authenticate to Sam, who is a server.  Suppose that, to authenticate, Alice is going to use your scheme to send a copy of the root password to Sam (encrypted and then signed); if everything checks out, Sam will conclude that Alice knows the root password and should be granted full access to the server.  Sounds reasonable, right?  But now look what can go wrong.  Mallet can intercept Alice's encrypted-and-then-signed packet, strip off Alice's signature, append her own signature, and forward it to Sam.  Sam will receive it and everything will check out: Sam can see that this was signed by Mallet and decrypts to contain the correct root password, so Sam will conclude that Mallet should be granted full access to the server.  That's bad.

The reason why an attack is possible in the latter example is that Alice and Sam were using the signature as a basis for taking credit: Alice was trying to take credit for knowledge of the root password, and Sam was willing to accept the signature as evidence for that.  However, encrypt-then-sign does not provide a basis for allowing the sender to take credit for knowledge of the contents of the message.

So, whether this scheme is adequate will depend upon the particular application you have.  Many applications only need authentication for the purpose of assigning responsibility: if something goes wrong, we know who to hold responsible (or, we know whose account to charge or whose quota to decrement), and encrypt-then-sign is fine for that.  But a few applications (the password authentication example I mentioned; auctions; and some others) use authentication to additionally allow the parties to take credit for knowledge of a message.  For those applications, vanilla encrypt-then-sign can be problematic.

There are ways to fix encrypt-then-sign so it doesn't have this shortcoming.  See the research literature below for details.

For more details on all of this, including what can go wrong as well as how to avoid these problems, you can read the following detailed explanation in the research literature:

Prudent engineering practice for cryptographic protocols. Martin Abadi and Roger Needham.  See Section 5.2 (but the entire paper is fantastic and a classic).
Security Protocols and their Properties.  Martin Abadi.  See Section 5.

Actually, Encrypt-then-MAC (EtM) is considered to be the most secure mechanism to achieve Authenticated Encryption (AE).
There is also a research paper by Mihir Bellare on this topic:
https://cseweb.ucsd.edu/~mihir/papers/oem.pdf

This is another resource from Dan Boneh's crypto class where the exact same thing is discussed (slide 29).
https://crypto.stanford.edu/~dabo/courses/OnlineCrypto/slides/07-authenc-v2-annotated.pptx

Also, another link on using the EtM paradigm:
https://moxie.org/blog/the-cryptographic-doom-principle/


Can we place the WOTS scheme into a Merkle tree structure? In post-quantum signature schemes that are (to put it simply) built out of merkle trees, they usually employ some sort of OTS scheme on the very bottom leaves.  I.e WOTS Winternitz scheme.
A relatively simple scheme such as Merkle is making a bunch of Lamport/WOTS keys and putting them on a merkle tree.
Is it possible to instead put the WOTS scheme itself on a tree, where each leaf represents a byte value, and where each leaf is a simple chain of 1 hash?
By tripling the computation required to make a single use WOTS key, it becomes a potentially finite use key, and you don't have the problem of being able hash forward that is usually resolved with checksums.
Are there some obvious security downsides to doing this?

This question is essentially "can we put the HORS scheme on a tree".  And the answer is yes, as it is the basically HORST.
The question adds confusion by mentioning a Merkle tree and not mentioning an index.  The actual question is (or should've been) "can x HORS public key sets be put on trees with each HORS tree being used to sign each of the x bytes".
Maybe it is not normal to think of HORS/T as WOTS compressed (or Lamport inflated) on an index/tree, but I will leave the question in case it helps anyone else who does.

Yes, any one time scheme (such as lamport, WOTS) can be turned many time scheme by placing the public keys into a merkle tree leaves and considering the merkle root to be the new public key.


Getting the Encryption Function From the Decryption Function + Decryption Key + Encrypted Item Is it mathematically possible to always be able to get the encryption algorithm used to encrypt a certain item (file, number, text, ...etc.) by knowing the decryption algorithm that will be used to decrypt that item, the encryption key (i.e. private key), and (of course) the encrypted item itself? I.e. are all encryption algorithms reversible and have this hypothetical equality hold (going to left decryption, while going to right is encryption), while still being able to get the method to go either way (right or left) if I know the other way: encrypted item + key <=> decrypted item?  I am referring to reverse engineering an encryption/decryption algorithm from knowing the other one in both symmetric and asymmetric encryption/decryption algorithms.

Every encryption is reversible, that's why most security relies on hashing in place of encryption.


What alphanumeric string length can be used to guarantee no hash collisions from CRC-64? If I'm hashing alphanumeric strings (chars in the set 0-9, a-z, and A-Z) with a CRC-64 hashing function, how long can my strings be while guaranteeing no hash collisions?

Stated differently: If I have a set of all CRC-64 checksums computed from alphanumeric strings  $0$ to $N$ bytes, how large can $N$ be before I see a collision in the set?

If you have 62 chars you can transform 62 letters ($10+26+26$) in 6 bit number (approx). CRC is guaranteed to be unique mapping (Injective function) as long as input is shorter than output  – you can have at most 10 letters, but not 11 since $62^{10} < 2^{64} < 62^{11}$.

It same goes whit most other hash functions. Lets say that you have hash function that takes only 64 bits and makes 64 bit output and is bijective (like a symmetric cypher). That mean you will not have collision as long as your input is shorter than 64 bits.

If you have mappings from all 64 bit inputs you are 100% sure that each new input will produce collision (because there is no value that is unused)

This is classical Birthday paradox problem and the linked Wikipedia article has a nice set of approximations that help you evaluate the chance of collisions. Of course, this applies to random choice of strings only. It's not possible to guarantee against collisions even when two strings are involved - there will be some very low probability even for two strings.


Which characters to take into account when calculating unicity distance? I need to calculate the unicity distance of a block cipher. Assuming I know that the plaintext is an English message I considered using 53 as the size of the alphabet, since the message could contain lowercase ans uppercase letters from the english alphabet, as well as whitespace.
Would this be the right way to approach this calculation?

Thanks in advance.

The alphabet size you need to consider, when calculating the unicity distance, is the size of the ciphertext alphabet.  This follows from the definition of unicity distance, as the amount of ciphertext needed to rule out all but one of the keys.*

For a classical cipher that only encrypts letters to letters, and ignores spaces and case distinctions, the alphabet size would be 26 (or possibly less, e.g. if I and J are merged together).
For a cipher that uses exactly the alphabet you described (upper- and lowercase letters and spaces) for both plaintext and ciphertext, the alphabet size would be 2 × 26 + 1 = 53.
For a modern cipher that outputs one 8-bit byte for each plaintext character, the alphabet size would be 256.
For a hypothetical cipher that only outputs 7-bit bytes, the alphabet size would be 128.

Note that, in the formula $U = H_k / D$ for the unicity distance, the per-character redundancy $D$ should really be interpreted as the number of bits of information revealed by one additional ciphertext character.

This can be calculated as the number of bits encoded by one ciphertext character (i.e. as log2(alphabet size), if we assume the ciphertext to have no redundancy), minus the number of bits of entropy per plaintext character, assuming that each ciphertext character decrypts to one plaintext character.  For ciphers where this is not always the case, like the VIC cipher or other fractionating ciphers, things get more complicated.

(Another example of a fractionating cipher would be a modern block cipher in a mode like ECB or CBC that always encrypts or decrypts one full block at a time.  For such ciphers, it's arguably more meaningful to calculate the unicity distance in units of blocks rather than characters.  Of course, you can then convert the result back to, say, bytes, and typically get the same result as if you'd assumed a one-byte block size to begin with.  But you still can't really decrypt a partial block with such a cipher — except by brute force iterating over the missing part of the block, which makes your already slow brute force attack even slower.)

It's also worth noting that the whole concept of a constant "plaintext entropy per character" is somewhat nonsensical, since it's not really fixed — typically, the more plaintext you already have, the easier the next character is to predict (and, thus, the less entropy it carries).  The plaintext entropy also depends strongly on the assumed distribution of plaintexts, and, in practice, on how good the attacker is at recognizing valid plaintexts.  Thus, reasonable estimates for the unicity distance of the same cipher can in fact vary widely, depending what assumptions one makes.

*) In fact, this "casual" definition I gave has a subtle error: for most ciphers, there is no amount of ciphertext that can be guaranteed to rule out all keys but the correct one.  Rather, the usual formula for calculating the unicity distance gives approximately the amount of ciphertext needed to reduce the expected number of false positives (i.e. wrong keys that randomly yield a plausible decryption) to one.

This means that, if you have exactly one unicity distance worth of ciphertext, and try to decrypt it with all keys by brute force, you will, on average, end up with two keys that give a plausible plaintext — one correct key, and, on average, one false positive.  To actually be reasonably sure of getting no false positives at all, you'll need more than one unicity distance of ciphertext.

Assuming, you only have 7 bit ASCII characters (since you are using a block cipher, I assume the use of a computer), you have to consider:

Each character takes 7 bit
English language has about 1,5 (according to wikipedia) bit entropy per character
Considering both upper and Lower Letter cases is not necessary, because in almost any case, the language allows just one of them. Considering the character case does not increase the languages entropy per symbol.

$\Rightarrow$ Redundancy is about 5.5 bit per character.

Then you need the keysize of your block cipher, and use the formula

$$U = H(k) / D$$
With distance $U$ (in characters), Entropy  $H(k)$ of the key (in bit), and redundancy $D$  (in bit per character). (formula taken from the wikipedia article).

With 128 bits in the key, this is only $\approx 23.27$  characters.


If you have a file and XOR every bit with a random bit, can you extract any information? Say you have a file that is not random, and you XOR every bit with a random bit (not pseudo, but really random). Can someone who sees only the result extract any information from it? Obviously, it won't be 100% accurate, but I imagine you can do some sort of stochastics and get a vague idea. If yes, how? If no, is there a mathematical proof?

This cipher is called a one-time pad. It is unbreakable ("perfect secrecy") assuming that:

The pad (the collection of random bits) really is truly random
The pad is never reused to encrypt other messages

So, no information can be extracted from $\text{file} \oplus \text{random bits}$.

The basic idea of the proof is that an attacker can test every possible key, but they have no way of knowing which plaintext is actually correct. If I encrypt "attack" with a one-time pad, then any six-character string could just as equally have been encrypted in the first place.

If the file has been crafted deliberately to survive this form of damage then yes you should be able to recover your data.

There are many quite simple methods from adding CRCs to replicating the data multiple times.

There are other possible routes to recovery. If for example the file was an ASCII text file then it may be possible to recover something close to the original data by reasoning and dictionary work.


Is it possible to use the root function to attack RSA? Sorry for my silly question, but I have some doubts on this point. I'm trying to explain it better with an example.

Suppose you use RSA to sign a package and you have the public key. If the signature is generated by the server with its secret key you are able to decipher it because you have the public key and verify the integrity of your package. Suppose I make a "fake" package and I'm able to create a correct signature like this:

00 01 FF .. .. FF 00 ASN.1 SHA1

due to the deciphering process:

cleartext = C^e mod n

I can encrypt my signature in this way:

C mod n = root(cleartext,e)

and make a correctly padded signature without knowing the private key?

Example:

e = public exponent = 3

C mod n = cubicroot (cleartext)

If root is just the function from calculus, then

at most ceil(root(n,3)) elements cleartext of  {0,1,2,3,...,n-2,n-1}

are such that root(cleartext,3) is an integer
and
when its output is not an integer, that output is not a valid signature,

since valid signatures must be elements of  {0,1,2,3,...,n-2,n-1}

.

If root is modular, then for carefully chosen large moduli n, there's no publicly known

feasible classical way to have a non-negligible probability of computing root.

However, quantum computers change things quite significantly.

You can do this. But only if you can solve the discrete logarithm problem!
Your "root" function actually has to find the group element c such that c^e = k where c and k are group elements of the group Z mod n and e is a natural number.

If you can find an efficient implementation of such a function, you will become very famous.


Now that quantum computers have been out for a while, has RSA been cracked? D-wave systems has released a commercially viable quantum computer. This means in theory, that all asymmetric encryption algorithms — such as RSA — are now useless due to the speed at which quantum computers can factor.

Has RSA been cracked yet? If not, why hasn't it?

The reason for our company's concern is an upcoming product that relies heavily on cryptography, and a significantly large number of hackers may attempt to break it. If the code was found to be insecure, it would be a huge problem for our company, our users, and anyone on the Internet if RSA was found to be insecure.

Update: article on D-Wave recent announcement here

RSA has not been cracked.  No one has demonstrated practically viable computing that's anywhere in the realm of breaking RSA.  There is no reason to change any of your practices.

The first thing to understand is that D-Wave has a long history of
repeatedly making bogus claims to the popular press.  Experts in quantum computing have been criticizing and debunking D-Wave's claims for years.  (Try clicking each of the last seven words, for examples.)  So, this is not a company with a lot of credibility.

The latest news is that D-Wave has published a paper in Nature that describes very limited progress towards quantum computing.  It is not a full-fledged quantum computer.  It can't do general-purpose computation; it can only solve one algorithm.  In particular, it can't be used to factor numbers or break RSA.  It can't handle realistic problem sizes; it only has 8 qubits, so it can only solve toy-sized problems (problems that you could have solved with pencil-and-paper anyway).  There is no evidence that it is faster than classical algorithms.  It's not faster than existing classical computers.  It does represent a step forward, but it's a limited step.

Researchers have been studying quantum computing intensely over the past decade or so.  There has been some progress, but it has been slow, and building a working quantum computer will require us to surmount some fundamental challenges (e.g., decoherence) that today no one knows how to deal with.  D-Wave gets a lot of press (mostly because they make irresponsible statements to the press to hype their work beyond its true importance), but others have made more significant contributions.

You use the phrase "commercially viable quantum computer".  That's not a useful phrase.  Please understand that D-Wave has not demonstrated a viable quantum computer.  D-Wave may have sold something to one or two customers, but that doesn't mean they have licked the quantum computing problem or that their claims therefore necessarily have any validity.  Snake oil salesman managed to sell their stuff to plenty of customers, too, but their claims were invariably bogus.

If someone did build a working quantum computing that scaled to an unlimited number of qubits, and solved the decoherence problem, that'd be different: in that case, we'd have to move away from RSA, pronto.  But we're a long ways away from that.  Right now, it's an open question whether we'll see such a quantum computer in our lifetimes (or even if it will ever be possible to build one) -- quantum computing experts like to debate questions like those over drinks.  I suspect, if general-purpose quantum computing is possible, we'll have plenty of warning before quantum computers that can threaten RSA become readily available.

So, in short, no, you don't need to change your strategy or drop RSA.  I wouldn't.  Continuing to use RSA is perfectly reasonable and in line with industry practices.

There still is no general-purpose quantum computers available at the time of writing this. As soon as Shor's algorithm and quantum computers become available, it will be possible to crack RSA.


Is there any alternative for extended euclidean algorithm to perform modulo division? I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division.

It appears the that extended euclidean algorithm takes almost 90% of the computation time for the whole operation. It is slowing down the entire operation.

Can anybody suggest me an alternative approach?.. Or if someone have already implemented it, tell me how did you manage to reduce the time taken??

For increasing speed, you should use of  "Barrett reduction" and "Montgomery multiplication". For more detail you can see "Guide to Elliptic Curve Cryptography". Also you can use "MAGMA". This program is  one of the best and fastest program for elliptic curve.

If I understand you correctly, you wish to compute $P-Q$ where $P$ and $Q$ are elliptic curve points. If you were working in a subgroup of $\mathbb Z_p^*$, then in order to compute $\frac{h_1}{h_2}$ then you indeed need extended Euclidean in order to find the inverse of $h_2$ and then multiply that with $h_1$. However, in elliptic curve groups, it is trivial to find $-Q$. Specifically, let $Q=(x,y)$ where $x$ and $y$ are in the underlying field. Then, $-Q=(x,-y)$. Thus, all you need to do is to take the negative of $y$ in the underlying field, and then add the result with $P$. This is therefore very fast.


How long does it take to crack DES and AES? Suppose that a single evaluation of a block-cipher (DES or AES) takes 10 operations, and the computer can do $10^{15}$ such operations per second.

How long would it take for to recover a DES key, using a brute-force search? How about a 128-bit AES key?

Assume that 1 evaluation of {DES, AES} takes 10 operations, and we can perform $10^{15}$ operations per second. Trivially, that means we can evaluate $10^{14}$, or about $2^{46.5}$ {DES, AES} encryptions per second. This is a simplistic view: we are ignoring here the cost of testing whether we found the correct key, and the key schedule cost.

So on our hypothetical machine, a 56-bit DES key would take, on average, $2^{55}/2^{46.5} = 2^{8.5} \approx 362$  seconds to find. Similarly, a 128-bit AES key would take $2^{127}/2^{46.5} = 2^{80.5}$ seconds $\approx 2^{55}$ (or approximately $36$ quadrillion) years to find.

It depends on the implementation. I just cracked one in about five minutes using Task Manager and a hex editor.
It was a commonly used public domain implementation, but free (so probably not a good example).
Just took a dump of the process after it ran and searched it for my key. Looked for associate memory fragments surrounding the key. Now I can find the key for anyone running that implementation.
Buy a good program that does not do a sloppy implementation.


Construct another ciphertext that decrypts to same message without knowing key in Elgamal I read about ElGamal from various resources and I was wondering if the following is true. Would appreciate if you could elaborate on it so I can understand better:

Is it possible to construct, given an encrypted message $c_1=E(m)$, another encrypted ciphertext $c_2$ that will be decrypted to the same message without knowing the key that was used for the encryption? I mean to create a $D(c_2)=m$ where $c_1 \neq c_2$

I am asking this because ElGamal from what I understand, this cryptosystem is not defined as injective because the results of the encryption depend on some random value.

To elaborate further on my thoughts: I think that ElGamal is not deterministic in the way each message can have several legal encryptions: for each of the $p-1$ of $k$, there would be a different encryption, but of course, the decryption will be reliable and return the same decrypted message: it will return the same $x$ without dependency on chosen $k$. So basically,

$x\bmod p = x\cdot b^k\cdot (b^k)^{-1}$ but $ x\cdot b^k =y_2$ and

$(b^k)^{-1} = (\alpha^{k\cdot a})^{-1}$, and $(y_1^\alpha)^{-1}=(\alpha^{k\cdot a})^{-1}$.

So we get $x \bmod p =(y_2)(y_1^\alpha)$. Basically to encrypt we only need $(p,\alpha,b)$ and to decrypt we need the private key $a$.

I would very much appreciate understanding this.

The key is here the probabilistic Encryption

  Probabilistic encryption is the use of randomness in an encryption algorithm, so that when encrypting the same message several times it will, in general, yield different ciphertexts

The first probabilistic encryption was proposed by Shafi Goldwasser and Silvio Micali Probabilistic encryption & how to play mental poker keeping secret all partial information in 1982. You randomize the encryption with a random for each message so that even the same messages get different encryptions.

This is why we call encryption can be probabilistic, but the decryption is deterministic. A plaintext can have  different encryptions but all must decrypt to the original plaintext

To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.

  I think that ElGamal is not determinstic in the way each message can have several legal encryptions:

Yes, ElGamal is not deterministic. During the encryption, we select a random value for the encryption that makes each encryption different for the same ciphertexts. During the calculation of the shared secret, we select a random $k \in\{1\ldots q-1\}$ and continue with the following parameters; $(G,q,\alpha,b)$ as the public key;

$G$ is the cyclic group
$q$ is the size of $G$
$\alpha$ is the generator of $G$
$b=\alpha^a$ where $a$ is the private key.

Then the encryption performed as following;

select a random $k \in\{1\ldots q-1\}$
compute $s = b^k$ - the shared secret
compute $c_1 = \alpha^k$
compute $c_2 = m\cdot s$

If we encrypt $m$ with the random $k$ than the ciphertext pair is; $$(c_1,c_2)= (\alpha^k, m\cdot s)$$ Encrypting wiht a another random $k' \neq k$ will result in a different ciphertext; $$(c'_1,c'_2)= (\alpha^{k'}, m\cdot s'=b^{k'})$$

  Rerandomization: How to create new encryption of this cyphertext without knowing the plaintext and private key.

To rerandomize a ciphertext, take a new random $k' \in\{1\ldots q-1\}$ and calculate $b^{k'}$ and $\alpha^{k'}$ now mutiply the pair.

$$(c_1 \cdot \alpha^{k'},c_2 \cdot b^{k'}) = (\alpha^k \cdot \alpha^{k'}, m \cdot b^{k} \cdot b^{k'}) = (\alpha^{k+k'}, m \cdot b^{k+k'}) = (c_1'', m \cdot s'')$$

Therefore the new encryption is based on the combined shared secret which is $b^{k+k'}$. Of course, there is a problem that $k+k'$ can exceed the $q-1$, however that is no problem since the little Fermat theorem.

The two ciphertexts are different since $\alpha^{k+k'} \neq \alpha^{k}$.

Decryption:

$s'' = (c_1'')^a$, $c_1'' = \alpha^{k''}$ then $(c_1'')^a = \alpha^{xk''} = \alpha^{k''}$
Compute $s''^{-1}$ by ext-GCD.
Compute  $m=c_{2}\cdot s''^{-1} = m \cdot s'' \cdot s''^{-1} =m$

Therefore the rerandomization works.

So in an ElGamal cipher text there are two pieces of information. A typical cipher text looks like this: ($g^b$, $mg^{ab}$)

So the answer to your question is it depends on how much you know about this cipher text message. You said you don't know the $g^{ab}$ (which is what most people would say is the key in this encryption), but suppose you know $m$, then of course. You can generate a different cipher text and here is what you do.

Choose random $c$ (different from $b$).
Grab $g^a$ (public key) from the receiver, compute $(g^a)^c$, compute $g^c$
Compute $m \cdot g^ac$
You have a new cipher text ($g^c$, $m \cdot g^{ac}$)
You send it, the recipient gets it, it will go compute $(g^c)^a$, then compute $g^{-ac}$, with that he can get m. Your new (and different) cipher text just decrypted into the same message.

On the other hand if you don't know m to begin with, (for example, you intecepted ($g^{ab}\cdot m$, $g^b$) from wireshark) then after a few minutes whiteboarding I can say I haven't found a way to do what you asked.


How to explain indistinguishability obfuscation (iO) to my grandmother? At the risk of oversimplification, how do I explain indistinguishability obfuscation (iO) to my grandmother?

iO removes all metadata from the program.


Generate Elliptic Curve Private Key from User Passphrase? I'd like to generate a private elliptic curve key from user input like pass phrase. Is the best way to do this with a key derivation function like PBKDF2? Is there a better way?

Edit (based upon @poncho's questions)

To be specific, this is for a Bitcoin ECC private key. It seems to me that if a user picks a passphrase like puppies, it makes sense to try to use PBKDF2, Bcrypt, or Scrypt to increase entropy.

Something like...

eccPrivateKey = pbkdf2(HMAC−SHA, "puppies", randomSalt, 10000, 256)

right? Should any inputs or outputs be hashed? So, is it acceptable (security perspective) for the output of the pbkdf2 to be the private key?

@poncho, hopefully my use case implicitly answers your questions regarding the brute forcing. i.e. don't care how long it takes to generate as long as it's under a few seconds. Care very much about dictionary and precomputational attacks.

Using PBKDF2/Bcrypt/Scrypt might be the least-bad way, but that doesn't mean it's a good way.  If your passphrase is puppies, it doesn't matter whether you use PBKDF2, Bcrypt, or Scrypt: you've got serious problems.  If someone tries to crack your key, you're going to be toast: your key will be cracked within minutes.

Bottom line: this sounds like a bad idea to me, if there's any possibility at all that the passphrase might be weak (which, in practice, there will be).
I would not use this to protect my money.

Instead, you should be generating a truly random or cryptographically-strong random number for the private key, then storing the private key somewhere safe.  If you want to store the private key in encrypted form, you can derive a symmetric encryption key $K$ from a passphrase and store the private key encrypted under $K$ (though please understand that this will likely be vulnerable if someone manages to steal a copy of the encrypted private key).

I'm going to assume the question asked is the question you want answered.   Enough people have responded as if it's bad question.

In order to secure a weak passphrase you must use a key derivation function.   The problem is that KDFs are trumped quickly by Moore's law.
You should compute the maximum value for the KDF based on the amount of time it takes on the target architecture.   If it takes one second to compute your key, brute forcing a 7 letter password will take 5000 years or so.  Even assuming Moore's law, and assuming an attacker has access to 1000 machines, that should be OK for a year or so.    Setting it to a few seconds is probably good enough for many applications where the value of the data could not possibly justify the attack.
Despite what others say, if forward-compatibility doesn't matter ... a KDF/derived private key is just as good (bad) as a KDF/encrypted private key with a weak password.  Both are private.  The only bad thing is "future proofness".   It can't be "re-derived" without also changing the public key.   Whereas an encrypted private key can be re-encrypted... moved offline, etc.... leaving the public key unchanged.
In a way, however, the idea that the private key can be strengthened later is a weakness of traditional public/private key management.   Far better for a weak key to always remain known (privately) as weak, and any new, stronger keys to be published and possibly signed as published by a prior weak key.   For bootstrapping into the future, this is far superior.   So maybe we should consider always using KDF's for private keys... rather than encrypting them, and just be far more fluid about re-deriving them when the user wants to change a password.


AES-CTR-MAC alternative I have to send small (~10 bytes) authenticated messages over an insecure channel. I was thinking of an alternative to the "conventional" AES128-CTR-MAC, which will take 16 bytes for the CT and additional 2 or 4 bytes for the MAC. The motivation is that I'd like to reduce the message size as much as possible.

My alternative is to use a nonce and a counter, pass it to a HASH function, xor with the PT, and then AES encrypt. This would produce the CT.

Since PT is small, I was thinking off zero padding it (with two or 4 bytes).
Then on decryption, I can compare the zero padding and use it as an authentication.

As I see it, this method is not prone to "bit switch" attack (as changing the CT will totally ruin the PT).

Do you think it's a reasonable way to do authentication? Is it enough to use a plain HASH function, or is it better to add a key to the HASH?

If, in addition, I also want to authenticate a non encrypted part of the message, It is OK to concatenate this message to the HASH input?

In addition: The transmitter and the receiver are time synchronized. and keep their internal (and equal) counter value. on each transmission, the transmitter and receiver increment their counter. The message is sent once every 10 seconds, and the receiver will accept only one packet on scheduled time. That way, the attacker can't brute force the MAC.

I can see at least one big issue with your own scheme: the attacker could cycle through as many counters until one is found that produces the same bits in the hash at the location of the padding bits used for authentication. In that case the authentication would succeed with a different nonce / counter. This problem also disallows additional authenticated data to be added to the scheme. This would be fixed by using HMAC instead of a hash. When validating the padding bits I would use a constant time compare to be on the safe side (I don't see a direct issue, but better safe than sorry).

You need to pad to the end of the block anyway otherwise you cannot XOR with the hashed IV. So you should at least use as many zero bits as possible. For two bytes you have a chance of one in $2^{16}$ that a random message is accepted. That's too large for most cryptographic systems.

So for a fixed sized message you could use 4 bytes minimum, giving you a chance of one in $2^{32}$ - somewhat over 4 billion in the short scale - to accept a random message. Even then it would be a good idea to implement additional ciphertext messages. Your messages would 12 bytes of course, as the AES block size is 16 bytes in size. The larger the padding the better.

Truncating a MAC (over the ciphertext) is common. It has the same problem as validating the padding in your scheme: if you check too few bits then the message may be accepted with a probability that is considered too high. It has the advantage of being secure for variable size messages, at the obvious cost of bits compared to your scheme.

Older triple DES schemes usually use 4 bytes / 32 bits. This could be OK if an authenticated session is broken if a bad packet is received, but remember that sending $2^{32}$ random messages is commonly not out of reach to an attacker.

I'd say that having a 10 byte cipher text (for a 10 byte message, there is no need to use 16 bytes for a 10 byte message) for AES-CTR and a 4 byte MAC is more secure than your proprietary scheme. CCM and EAX are ready made AEAD schemes that could be useful in your situation. They rely just on AES and allow shorter tag sizes without losing too much security, and they allow additional authenticated data as well.

The addition (having the counter and time synced) does make it harder for an attacker to have an invalid message accepted. However, it still doesn't disallow attacks on additional authenticated data that gets hashed. It should be noted that keeping a nonce and the time synchronized can be a deceptively hard problem. An attacker is often capable of power cycling devices, slowing down clocks etc.

Truncating the MAC tag is done not so rarely. The IANA has a registery of AEAD algorithms with truncated MAC tags, but usually they're not shorter than 64 bits.

What your diagram describes is not so different from that used in the key wrapping mode as specified in NIST SP 800-38F. They append short constant values to the plaintext, then use a key wrapping transformation (built from block ciphers such as AES) to generate the ciphertext.


Security limits of password-based encryption A reasonable way to do password-based encryption is:

put the passphrase¹ and nonce in a well-parametrized memory-hard iterated hash function like Argon2, to derive a key 128-bit or larger.
output the nonce, followed by the ciphertext per some strong authenticated encryption; AES-GCM-SIV or ChaCha20+Poly1305 comes to mind.

Legitimate decryption with the password is trivial. The best generic attack enumerates passwords from most to least common, starts to decrypt, obtains the start of the plaintext, tests it per some criteria and moves to the next password until one matches. Assume known plaintext at the start of the file².
The security depends on the good choice of password and the parametrization of the iterated hash. It's very hard to give figures, but assume 32-bit² entropy for password and a few seconds of Argon2 on one's PC. However one counts, the security in bits is far from academically acceptable levels.
Main question: Can we do better, assuming a plaintext of significant size, say $n=2^{20}$ or $2^{30}$ bits? How much better? What's the theoretical limit of the gain we can get from large $n$?
I'm thinking of using an all-or-nothing transform, perhaps approximated by 2 passes of AES-128 in PCBC mode, and two keys derived from the password, because we can at almost no cost. That idea is not new: ref1; ref2. But I still hope for an answer that takes into account memory-hardness.

Here is my work so far, very tentative. One can raise questions: criticize!
Taking the scheme at the start of the question as a reference method, let $t$ be the time (in seconds) spent in password-to-key conversion by Argon, $m$ the memory (in bits) used for that, $c$ the throughput (in bit/s) of the cipher itself, and $\ell$ the message length (in bits). The total time to encipher is thus about $T=t+\ell/c$. We do not want to wait more than that.
There is something to be gained by loading whatever of the plaintext fits in memory, and spending the time $T=t+\min(\ell,m)/c$ on password-to-key transformation while enciphering the plaintext at the same time in an hypothetical iterated-all-or-nothing memory-hard transform, performing the encryption for free; then using the key thus produced for the rest of the plaintext. If we assume there is at least 128-bit of entropy in the part of the plaintext that fits memory, which is a plausible assumption, good: that makes the rest essentially invulnerable until the password is found by crunching all the beginning.
Assuming our iterated-all-or-nothing memory-hard transform is as good at password-stretching as Argon2 is, I tentatively get as gain on "stretched password entropy" (or, more rigorously, for the base-2 log of the multiplicative factor for attacker cost):
$$\log_2\left(1+\frac{\min(\ell,m)}{c\,t}\right)\text{ bit}$$
That's next to nothing when $\min(\ell,m)\ll c\,t$, and otherwise grows with $\ell$ until reaching a maximum at $\ell=m$, then stops growing.
Assuming $t=2^2$ (4 s), $c=2^{32}$ (512 MiB/s), $m=2^{36}$ (8 GiB), we gain ≈2.32 bit. That's much less than a decimal digit in a random passcode (≈3.32 bit), and at best in the order of a character more in a passphrase.
The faster the cipher we replace, the less gain. The more RAM, and until the plaintext does not fit, the more gain.
Unless I err, asymptotically, when we double the RAM and until all the message fits in there, we seem to quadruple rather than double a memory-bound attacker's cost. I'm still scratching my head for CPU-bound.

¹ Rather call it that: it is easy, unobtrusive, and has gone miles to improve security of PGP.
² In practice, a compressibility test will do if there is even mild redundancy in the plaintext.
³ The only power of two in [28-44].

An $O(\log l) $ cost for $l \le m$ seems a little simple given the many components (Argon, AES, hard & soft optimisations and bounded RAM & I/O).
Have you considered an empirical simulation?  You could lash something together in your favourite programming language, set all soft and hard parameters to reasonable levels and just see. So either an iterated approach, or a Monte Carlo simulation. It might at least suggest a real world relationship between all the parameters.
I don't know whether they'd talk to you about scale, but is it worth asking someone who actually does this? Apparently the Inmanis appliance has 'monstrous performance'.
P.S Whilst the application of your theory to a singular very large message seems sound on the face of it, the password wouldn't be recovered from such (knowing the presence of AoNT). Clearly you'd attack the shortest  message which might be "Toodles" covered by the same password. Don't know whether that has any bearing on what you're trying to demonstrate.


P = NP and current cryptographic systems I've recently heard some people claiming that if the fact that P = NP is proven, most (all?) the current cryptographic algorithm considered secure like RSA will be unusable in secure systems.

My question is :

1. If P = NP is proven TODAY, will a RSA key (let say 3072 bits) be still enough to ensure a certain amount of security.

2. If not, what could we do to have at least the same amount of security (take a larger key length? a stronger algorithm?)

A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...)

However, it would just mean that no scheme can be provably secure. It does not mean that all schemes would be broken in practice. It might even be possible to adapt our definitions of security in a meaningful way.

In particular, it is very much conceivable that a proof of P=NP would be non-constructive. Such a proof would not help in any way. It would just mean that there exists an algorithm to efficiently break RSA (for a theoretical definition of efficiency, i.e. in polynomial time) but that does not mean that we know said algorithm. And even if the algorithm is known, it might not be efficient in practice.  An algorithm running in  $\mathcal{O}(n^{2^{100}})$ is technically a polynomial time algorithm, but it isn't very helpful.

So in conclusion, the question whether some keysize would still remain "secure" or how we could regain some measure of security cannot be answered in general, as it depends on the exact nature of the proof.

Here is a posting from two decades ago about why P=NP has nothing to do with cryptography:

http://theworld.com/~reinhold/p=np.txt


What is the entropy of a Mersenne Twister (MT)? From Serious Cryptography:
"Entropy is maximized when the distribution is uniform because a uniform distribution maximizes uncertainty: no outcome is more likely than the others. Therefore, n-bit values can’t have more than n bits of entropy."

The MT strives to have as uniform a distribution as possible, so one would think the entropy is maximized and equal to the bit length of the seed.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

These two ideas seem to contradict each other.

But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

The subsequent distribution is not, in fact, independently uniform.

Given 624 32-bit outputs $$V = V_1 \mathbin\| V_2 \mathbin\| \cdots \mathbin\| V_{624},$$ I can deterministically recover the Mersenne twister state by $$S(V) = \tau^{-1}(V_1) \mathbin\| \tau^{-1}(V_2) \mathbin\| \cdots \mathbin\| \tau^{-1}(V_{624}),$$ where $\tau$ is the tempering transform, and then compute the next output by deterministically running the generator $G$ on the recovered state $S(V)$.  If the $V_i$ were independently uniformly distributed, we would have $$\Pr[V_{625} = G(S(V))] = 1/2^{32},$$ but if the $V_i$ are instead generated by the Mersenne twister with uniform random initial state, we have $$\Pr[V_{625} = G(S(V))] = 1.$$

This test—evaluate whether $V_{625} = G(S(V))$—will distinguish the Mersenne twister under a uniform random initial state from a uniform random string with high success rate.

Does this nonuniformity matter for the Monte Carlo physics simulation you're doing?  Perhaps not: your physics model is unlikely to, by happenstance, interact with the Mersenne twister output generation function $G$ in a way that would be a problem, because physics itself is usually not adversarially trying to screw you up personally, no matter how much the years of pain in grad school might make it seem.

On the other hand, if there is an intelligent adversary, as we assume in cryptography, that intelligent adversary will exploit this relation to decipher your messages, steal your money by forging signatures, etc.

In other words, the Mersenne twister is designed to appear uniform to stupid algorithms that don't even know it's the Mersenne twister they're trying to distinguish, but falls flat on its face when it trips on an adversary who knows it's the Mersenne twister but just doesn't know the initial state.

Your question encompasses both the cryptographic and information theory definitions of entropy. In cryptography, one is generally concerned with unknown entropy.

  Entropy is maximized when the distribution is uniform...

This is true and holds whether the sequence is known or unknown.  In the standard $ H(X)=-\sum_{x \in X} P(x) \log_2{P(x)} $ formula, the summation is maximised when all $ P(x) $ are equal. It drops as the distribution moves away from uniform to other types (Poisson, Gaussian, etc.) You can envisage it as related to the area of the sequence's histogram, as long as the bins remain the same.

  But the MT becomes entirely predictable after 624 iterations, at which point its entropy should be considered to be zero, but the subsequent distribution is still uniform.

Mostly correct.  Assume that the input to the MT is unknown (unknown entropy). MT therefore  will start generating unknown entropy. The ratio $ \frac{H_{unknown}}{H_{known}} $ will then linearly decrease from high to 0 as the output lengthens to 624 words. After 624 words, all future MT output will be entirely predictable and thus known. Yet according to information theory the known entropy will remain at 8 bits/byte as the distribution is uniform. Storage of said entropy would still require 8 bits/byte.  Unknown entropy useful for cryptography will of course then be zero.

Nobody at all does, but if you did use MT for cryptographic randomness, I suggest that one should reseed after 616 outputs, guaranteeing a 256 bit security level. There are other MT warm up nusances that make this a sub-optimal idea, but it illustrates the principle of entropy transforming from unknown to known.


PBKDF2WithHmacSHA512 Vs. PBKDF2WithHmacSHA1? I'm working on a Java authentication subsystem that specs the storage of passwords in the DB as PBKDF2-generated hashes, and I'm now trying to decide whether I should use SHA1 or SHA512 as PFR. I'm under the impression that the consensus is that SHA1 has some theoretical weaknesses, and that SHA512 should be chosen instead. However the standard javax.crypto package does not offer a PBKDF2WithHmacSHA512 implementation, how is that so?

For reference purposes, here’s my code:

private static final int HASH_BYTE_SIZE = 64; // 512 bits
private static final int PBKDF2_ITERATIONS = 1000;

// generate random salt
SecureRandom random = new SecureRandom();
byte salt[] = new byte[SALT_BYTE_SIZE]; // use salt size at least as long as hash
random.nextBytes(salt);

// generate Hash
PBEKeySpec spec = new PBEKeySpec(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1"); // this throws a NoSuchAlgorithmException if I replace with "PBKDF2WithHmacSHA512"
byte[] hash = skf.generateSecret(spec).getEncoded();

// convert hash and salt to hex and store in DB as CHAR(64)...

Hash algorithm strength is important, but it is not so important in key derivation functions. It is unlikely that even if SHA-1 is broken that it would influence the security of PBKDF2. You are better off using SHA-1, and increase the iteration count up to a level that is tweaked for your specific configuration.

If you must, you could use Bouncy Castle to create an implementation of PBKDF2 with SHA-256. The internal security of the algorithm is not that important, if your server is relatively safe against side channel attacks (and for PBKDF2 it likely is). So using a non-certified open source solution would probably not compromise your security.

Your efforts are probably better spend elsewhere. Congratulate yourself on choosing a relatively good password based KDF, choose a 64 bit random salt and use a higher iteration count, and move on...

Note: if you want to protect against hardware accelerated attacks, you may want to consider scrypt instead of PBKDF2.

The Oracle JDK 1.8 contains PBKDF2 implementations for SHA-512 "PBKDF2WithHmacSHA512". This can be used for compatibility with other systems or for deprecating SHA-1 entirely.

...the standard javax.crypto package does not offer a PBKDF2WithHmacSHA512 implementation, how is that so?

Starting with Java8, there is support for PBKDF2With<prf> where <prf> can be any number pseudo-random functions, including HmacSHA512.

So it is now supported.

  Any thoughts?

What the others have said is good advice. If for some reason you really wanted to use PBKDF2 with HmacSHA512 in standard java, you can if you switch to Java8.


Should we trust the NIST-recommended ECC parameters? Recent articles in the media, based upon Snowden documents, have suggested that the NSA has actively tried to enable surveillance by embedding weaknesses in commercially-deployed technology -- including at least one NIST standard.

The NIST FIPS 186-3 standard provides recommended parameters for curves that can be used for elliptic curve cryptography.  These recommended parameters are widely used; it is widely presumed that they are a reasonable choice.

My question. Can we trust these parameters?  Is there any way to verify that they were generated in an honest way, in a way that makes it unlikely they contain backdoors?

Reasons for concern.
Bruce Schneier has written that he has seen a bunch of secret Snowden documents, and after seeing them, he recommends classical integer discrete log-based cryptosystems over elliptic curve cryptography.  When asked to elaborate on why he thinks we should avoid elliptic-curve cryptography, he writes:

  I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

This suggests we should look closely at how the "constants" (the curve parameters) have been chosen, if we use ECC.  This is where things look concerning.  I recently read a message on the tor-talk mailing list that seems to suggest the NIST curve parameters were not generated in a verifiable way.  That message examines how the parameters were generated:

  I looked at the random seed values for the P-xxxr curves. For
  example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90.  No justification is given for that value.

and ultimately concludes:

  I now personally consider this to be smoking evidence that the
  parameters are cooked.

Based upon my reading of FIPS 186-3, this appears to be an accurate description of the process by which the P-xxxr curves were generated.  So, should people be concerned about this?  Or is this just paranoia based upon loss of trust in the NSA?

See also these slides from Dan Bernstein and Tanja Lange, particularly pp.6-7, 8-10, 14-17 for further discussion about the NIST parameter choices.

Edit: I have made some tests and I found something weird. See at the end.

Initial answer:

At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent:

Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several representations, but they are all isomorphic).
Restrict yourself to prime values of m to avoid possible weaknesses by plunging into sub-fields.
Consider curves $Y^2+XY=X^3+aX^2+b$ where $b \ne 0$; this is the normal form of non-supersingular curves in binary fields.
You only want curves where $a = a^2$ and $b = b^2$, so that you can speed up computations with the Frobenius endomorphism (basically, you replace point doublings with simply squaring both coordinates, which is very fast).
When $a = 0$, the curve order is necessarily a multiple of 4; when $a = 1$, necessarily a multiple of 2.

Then you want a curve order which is "as prime as possible", i.e. equal to $2p$ or $4p$ for a prime $p$ (depending on whether $a = 1$ or $0$). For $m$ ranging in the "interesting range" (say 160 to 768), you will not find a lot of suitable curves (I don't remember the exact count, but it is something like 6 or 7 curves). NIST simply took the 5 of them corresponding to the $m$ values which were closest to (but not lower then) their "security levels" (80, 112, 128, 192 and 256-bit "equivalent strength"). There is no room for "cooking" here.

So I would say that at least Koblitz curves are demonstrably free from all these "cooking" rumours. Of course, some other people argue that Koblitz curves have some special structure which might be leveraged for faster attacks; and that's true in two ways:

Faster computations mean faster attacks, mechanically;
One can solve discrete logarithm "modulo the Frobenius endomorphism" which means that K-233 is about as strong as a 225-bit curve (because 233 is an 8-bit number).

I still consider such curves to be reasonable candidates for serious cryptographic work. They have been "in the wild" for more at least 15 years and are still unscathed, which is not bad, as these things go.

Edit: I have made a few tests, enumerating all Koblitz curves in $GF(2^m)$ for $m$ ranging from 3 to 1200. For each $m$, there are two curves to test, for $a = 0$ and $a = 1$. We consider the curve "appropriate" if its order is equal to $4p$ (for $a = 0$) or $2p$ (for $a = 1$) with $p$ prime (this is the "best possible" since the curve is always an extension of the same curve in $GF(2)$, so the curve order is necessarily a multiple of the curve in $GF(2)$, and that's 4 or 2, depending on $a$). For the "interesting range" of $m$ between 160 and 768, there are fourteen appropriate curves:

$m = 163$, $a = 1$
$m = 233$, $a = 0$
$m = 239$, $a = 0$
$m = 277$, $a = 0$
$m = 283$, $a = 0$
$m = 283$, $a = 1$
$m = 311$, $a = 1$
$m = 331$, $a = 1$
$m = 347$, $a = 1$
$m = 349$, $a = 0$
$m = 359$, $a = 1$
$m = 409$, $a = 0$
$m = 571$, $a = 0$
$m = 701$, $a = 1$

NIST's target was their five "security levels" of 80, 112, 128, 192 and 256 bits, and a curve would match that level only if its size is at least twice the level. So the standard curve for each level ought to be the smallest curve which is large enough for that level. This should yield Koblitz curves in fields of size 163, 233, 277, 409 and 571 bits, respectively.

Strangely enough, this matches NIST's choices except for the "128-bit" level, in which they chose $m = 283$ instead of $m = 277$. I don't know the reason for this. For both field sizes, the smallest possible reduction polynomial is a pentanomial ($X^{277}+X^{12}+X^{6}+X^{3}+1$ for $m = 277$, $X^{283}+X^{12}+X^{7}+X^{5}+1$ for $m = 283$), so neither field is at a computational advantage on the other is using polynomial bases (well, the 277-bit field is a bit shorter, so a bit faster). With normal bases, the 277-bit field is actually more efficient, because it accepts a "type 4" Gaussian normal basis, while the 283-bit field is a "type 6" (smaller types are better for performance). The list of all suitable Koblitz curves is easy to rebuild and, indeed, NIST / NSA did it (e.g. see this article from NSA-employed J. A. Solinas -- search for "277").

Why they chose the 283-bit field is mysterious to me. I still deem it very improbable that this constitutes "cooking"; this is a backdoor only if NIST (or NSA) knows how to break Koblitz curves in a 283-bit field and not in a 277-bit field, which not only requires an assumption of "unpublished big cryptanalytic advance", but also requires that supposed novel breaking technique to be quite weird.

The agency behind this openly emblazons "Nothing is Beyond our Reach" on the side of their spy satellites (NROL-39 for example).

The answer to your question is "No".  The reason that the answer is "No", is classified.

If you're still not totally certain that the answer is "No", please find any other job - security is not for the naive.


How can complexity be increased or decreased in AES? I have been studying data compression for a while. For educational purposes, after a lot of reading, I managed to create a software that performs encryption and authentication using AES256-GCM. However, I have now reached a point after which I cannot find a possible answer and this is confusing me.

My software allows the user to choose the "hardness" of the encryption, a value ranging from 0% to 100% (a scale). Nonetheless, I have not managed exactly how I could mingle the logic of "hardness" with the logic of AES. Yes, I have a lot of ideas about playing with the key, the IV, the resulting data and so on, but a point I have learned on this area is that you should never reinventing the well when there is already studies on the same aspects and whose results had been checked and rechecked over and over and over again.

Therefore, what would be the best way to perform such work? I seek for theory, not necessarily coding.

This begs the question, why would you in any real-world circumstance wish to reduce the difficulty for an attacker to break your cryptosystem?

To answer your question practically, the only reasonable way I can think of to accomplish this is to simply reduce the entropy in the key. At 100%, all 128 bits of the key are used. At 50%, 64 bits of the key are used, and the rest set to some static value (e.g., 0). At 25%, 32 bits of the key are used, and so on.

That said, I want to reiterate that there is no reason I can possibly conceive of to support such a feature, outside of sheer curiosity.

Edit: Note that this will result in an exponential decrease in security, which maps well onto how cryptographers typically think of the security of a system. Modern ciphers like AES-128 so strong that a 100-fold reduction in difficulty to break still leaves brute force well outside the realm of conceivable human feasibility ($\frac{2^{128}}{10^{2}} \equiv 2^{121}$).

Take a look https://en.wikipedia.org/wiki/Triple_DES

It is original DES with three different keys successively 3 × 56 = 168. In such way length of key increased 3x, but hardness much more.

You would use google for "Triple AES". My first try give me this:

Would a "Triple AES" (in the sense of how Triple Des works) serve for a dramatic increase in safety?


Reuse of a DH / ECDH public key I was wondering whether it is safe to use the same DH or ECDH key pair in more than one key agreement, particularly if these public keys are in a public registry. These public keys could be used by your counterparts (who also have their public keys in the same registry) to agree on a secret used to send you a message, even when you're not online. A user's public (EC)DH key is changed each time s/he goes online.

Is that system safe? Does reusing the same public key makes it more easy to solve its DLP?

EDIT : When I meant to use a public key in more than one key exchange, I meant it will be used with different counterparts.

Using DH when both sides have static public keys (always send the same message when running the DH protocol) doesn't make DLP easier. It does increase the value of the secret key.

There are some things to worry about. If the DH shared secret or one of the secret keys is compromised, the compromise is complete. This is mitigated if the static public keys are replaced often.

In ordinary DH, the shared secret is a one-time secret. With static public keys, you have a multiple-use secret. You need to be very careful when using this key.

You should also be aware that DH where only one side has a static public key is essentially equivalent to ElGamal encryption...

Why don't you just use RSA? It's the common solution for that problem. User $a$ sends a message to $b$, signs it with $SK(a)$ and encrypts it with $PK(b)$. Read more at the Wikipedia article about DH.

The main problem I see (even when using RSA) is: how to verify that the published public key really belongs to the intended recipient and not an attacker. Trust on first use, PGP-like key signing or some kind of central authority. Which raises the question: what does the network look like? That should also be taken into considderation.


Can you use a hash as a password? There are several methods of making a strong password, making it longer is one of them. now we also have hashing algorithms which have outputs of 512,
so i wonder, would it be safe to basiclly use a simple password like dog, and then use the for example 512 bit hash output as the password.

EDIT: out off all the answers i think i thought out something that would be secure so consider the following: if i write a program which hashes a word with a number that comes out of a cryptographiclly secure pseudorandom number generator(having a minimum of 5 hashes, and then use the out put as a password, for example: i use the word dog as word, then number generator provides me with a random number of 5 or higher which defines how many times it needs to be hashed. in this case, we got the numer 30 for example, then we hash the word dog 30 times with a secure hash function. then this would be a secure password against dictornary attacks right? because if they dont know how many times you hashed it, then trying a dictornary attack should become a much harder task to achieve, and for brute force: trying to crack  a 512 bit password with letters and numbers should be madness, and if you use a salt along side of it, it should become really secure. so if someone is able to write something like this, and combine it with a secure and encrypted password vault, then it should be a pretty powerfull tool for password creation and management. so this is basically the idea, feel free to point out things i missed or possible weaknesses :)

I'd say the key thing that you need to spell out to answer this question is this:

What information does the attacker have?

This ties to one of the basic concepts of cryptography, called Kerckhoffs's principle: "A cryptosystem should be secure even if everything about the system, except the key, is public knowledge."  (I recommend you read that page and take its lessons to heart, along with the security through obscurity entry as well.)

So if we apply Kerckhoffs's principle to your proposal, we would assume that:

The attacker knows that your password is the hash of some secret word that you choose, but not which word;
The attacker knows which hash function you used to hash this word, and how to compute this hash function.

Then we trivially conclude that this isn't any safer than just using the word as the password.  And since "dog" is a very common word in the English language, it's an obvious one for an automated attacker to try.

I'd say that in your question you are doing something that most laypersons do when they propose password rules or schemes like this one: you're assuming that the attacker won't know or guess the rule you're using to generate your password.  But:

You just told your idea to the whole Internet.
Even if you hadn't, there's a good chance that an attacker might think of the same idea.

So really, the best passwords are random passwords, because there's no rule that an attacker can use to predict them.

EDIT: Funnily enough, a few days before this question, Duo Labs published a security analysis of OEM PC software updaters (press release; PDF report), that contains this gem (p. 16):

  Unfortunately, the encryption utilized is RC4 with the pre-shared key “e8fded24af79202d7da48adefe4a3a04”, which is the MD5 hash for “Asus Live Update.” As this layer of encryption boils down to simple obfuscation that can be dealt with on the fly, it provides no security value.

This is almost perfectly analogous to the question's proposal:

Pick a secret passphrase ("Asus Live Update");
Hash it with a standard hash function;
Use the resulting hash value as an encryption key.

And yet the researchers, just from seeing the hashed value, managed to guess the passphrase and the hash function used to obfuscate it.  So there we have it, a documented real-life failure of the strategy.

So what if you hash a simple word (dog for example) and then you chose both the length of the password and where woud it start in the length of your hash. Even if you know the method you have to know both the word used and the numbers (starting letter and length) chosen which are both almost arbitrary. Maybe you could make an estimation of the length(since password lengths are quite standard) but i think it would be pretty damn hard to guess while the user just has to remember a word and two numbers.


Why can’t DSA be used for encryption? This question at StackOverflow mentions that DSA cannot be used for encryption. But both RSA and DSA can be used to generate public and private keys, right? Then why can't I use the DSA public key to encrypt?

DSA stands for "Digital Signature Algorithm" - and is specifically designed to produce digital signatures, not perform encryption.

The requirement for public/private keys in this system is for a slightly different purpose - whereas in RSA, a key is needed so anyone can encrypt, in DSA a key is needed so anyone can verify. In RSA, the private key allows decryption; in DSA, the private key allows signature creation.

The fact that RSA also can be used for signatures is a result of the textbook algorithm being a trapdoor permutation - in simple terms, this means the ciphertext and the plaintext are part of the same set space. It is not a requirement of a public key algorithm for this to be the case - public key algorithms just require trapdoor functions.

To reduce misunderstandings, I modified it, just talking about the very question and the encryption .

I will try to answer this question with the help of OpenSSL commands and add some explanations to them.

1. The RSA  algorithm can be used for encryption.

There is RSA encrytion command openssl rsautl in OpenSSL.

1.1. If encrypted by  the public key, and decrypted by secret key , this is called encryption.

This is the encryption procedure by OpenSSL

1.1.1.  The content of the file example.txt

 hello,openssl!

1.2.2. Encryption by public key  rsa_pub_2048.pub

 openssl rsautl  -inkey rsa_pub_2048.pub -pubin  -in example.txt  -encrypt >example_encrypt.bin

1.3.3. Decryption by rsa_pri_2048.key rsa_pri_2048.key :

 openssl rsautl -inkey  rsa_pri_2048.key -decrypt  -in example_encrypt.bin

2. But the DSA algorithm is different from RSA.

2.1. The DSA algorithm can theoretically be used for encryption according to its mathematical properties because DSA is based on the discrete algorithm, and it can be used for Diffie–Hellman key exchange.

So a number can be negotiated by the DSA parameters, and we can use this number to encrypt.
  (Just by the number itself, not by DES or AES.)

  For example, this is one of the ways to encrypt using the negotiated number.
  1. Since the number $K_M$ is negotiated by the two sides(Alice and Bob), they both know the number.
  2. Alice encrypt the message $x \in Z_p^* $ , $y \equiv x \cdot K_M \pmod p$
  3. Bob can decrypt the message $x \equiv y \cdot K_M^{-1} \pmod p$
  This algorithm is take form the book 《Understanding Cryptography》

2.2. But there is no such standard for encryption by DSA in engineering.

So there is no such encryption command in OpenSSL.

2.3. So DSA is only used for signing in engineering.

The openssl dgst command can alse be used by RSA and  ECDSA key. I just emphasize that there is no similar  openssl rsautl command  in DSA to encrypt directly.
   This is the signature and verification procedure by openssl in DSA.

2.3.1. Sign a file  file.txt by secret key dsakey_2048.pem

  openssl dgst -sha256 -sign dsakey_2048.pem  -out signature_2048.sign file.txt

2.3.2. Verify a signature  by secret key dsakey_2048.pem

  openssl dgst -sha256 -prverify dsakey_2048.pem  -signature  signature_2048.sign  file.txt

2.3.3. Verify a signature  by secret key dsakey_2048.pem

  openssl dgst -sha256 -verify pubkey_2048.pem  -signature  signature_2048.sign  file.txt

3. How does encryption is performed in HTTPS using DSA keys?

3.1. A big number is negotiated by the DSA parameters using Diffie–Hellman key exchange algorithm.

3.2. A symmetric encryption(such as AES) is used to encrypt by the big number.

This is the  Cipher Suite by the DSA in HTTPS, it called DH+DSS+AES.

     TLS_DH_DSS_WITH_AES_256_CBC_SHA256 (0x0068)
     TLS_DH_DSS_WITH_AES_256_CBC_SHA (0x0036)
     TLS_DH_DSS_WITH_CAMELLIA_256_CBC_SHA (0x0085)
     TLS_DH_DSS_WITH_AES_128_GCM_SHA256 (0x00a4)
     TLS_DH_DSS_WITH_AES_128_CBC_SHA256 (0x003e)
     TLS_DH_DSS_WITH_AES_128_CBC_SHA (0x0030)
     TLS_DH_DSS_WITH_SEED_CBC_SHA (0x0097)
     TLS_DH_DSS_WITH_CAMELLIA_128_CBC_SHA (0x0042)

3.3 So the encrypt is performed by  Diffie–Hellman Algorithm and AES, not by the DSA itself.


power consumption in a XOR I'm trying to understand how a XOR affect traces of power consumption in a Differential Power Analysis on smartcards.

What's the difference in energy radiated in a $1 \oplus 1$ and in a $0 \oplus 1$?

If I understand correctly we have a XOR gate, and if a $1$ is xored with a $0$ then electrons in the 1 branch just continue flowing thus we still have some energy compared to a $0 \oplus 0$.

The exact details depend on the logic family but basically The difference is that the charge representing those "1" bits need to be discarded somehow. This is done by switching the output to ground, 1^0 is 1 so no charge need to go away but 1^1 is zero meaning at least two gates get discharged to ground slightly raising its voltage due to the non zero resistance in the ground return path.

Though, this really depends on the logic Family, the effect of charging the output gate lowering vcc may be dominant in some like you say. But in most any mos family, some assymetry will be noticed. ECL is notably immune due to steering currents that always flow not charging capacitors.

Sounds like you are trying to develop or find a sophisticated side-channel attack against XOR encryption. Since XOR is my main type of encryption I also try to find brute-force and side-channel attack methods to test how secure or insecure my own XOR encryption algorithms are.

The XOR gate either passes an input bit to the output or flips the input bit in the output. Flipping a bit is probably a few clock cycles slower than passing a bit.

The first thing and experiment you would have to do is to check whether this assumption is really the case or not. In order to do so I would recommend to code your own XOR encryption function (in C++ or other language) and then add a timer which measures how long it took the program to execute or run through the XOR gate function in each of the two possible cases when input bit was either 0 or 1.

This way you could the test the clock cycle times per frame. As suggested by others the time difference may be so small that it has to be measured in nanoseconds precision. Most timer functions I know of in C++ and other languages, however, can only measure time down to milliseconds which is too slow for that kind of experiment, thus it seems impossible in my opinion to measure the time difference between each single XOR gate code execution. Unless someone can point me to a timer function (C++ prefered) which can measure systemtime in nanoseconds and output the time value into a variable.


RC4 Keylength Limits While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits.

Why is that? Is there a reason it can't have a lower or higher length?

The minimum of 40 bits is conventional; below 40 bits of key material, RC4 (or practically any cipher without some built-in key stretching) is just too unsafe.
At some point in history, in many countries, ciphers with a key above 40 bits where illegal in some usage (in USA: export; in France: use, sale, export); thus cipher designers wanting to prescribe something as secure as possible often used that 40-bit limit.

The maximum of 2048 bits is a consequence of RC4's key scheduling. Quoting Wikipedia's page on RC4

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

We see that 256 passes are made, and each pass manipulates 8 bits of key; above $8\cdot256=$ 2048 bits, extra key material would be ignored.

Anyway, array S[] remains a permutation of 256 distinct values, hence can hold a maximum of $\log_2(256!)\approx$ 1684 bits of entropy, and that key size limit of 2048 bits is only a practical issue when the key is not truly random in the first place.

In order to strengthen RC4 against weakness in its key scheduling / setup (leading e.g. to break of WEP encryption), it is advisable to stretch the size of the key material (e.g. to the maximum of 2048 bits) using a pseudo-random transformation (alternatively, or in combination, the first 256 or 512 bytes generated can be discarded). And if the original key is low-entropy (e.g. a password), it must be strengthened by a slow key derivation function in order to resist brute-force password cracking. Both can be done using scrypt with dkLen=256, and other parameters set as appropriate for the environment.

If you have to use the key several times, add a salt. A salt is a random number, that is added to the password, and transmitted (in plaintext) to the receiver. The reciever uses the salt in his password shedule, and gets the original stream. As the salt is different for every packet cracking gets much harder.

Example:
 User's password:Test (a very common password)
 Salt1: 42
 Key1: 42Test
 Packet1: 42[Encrypted data]
 Salt2: 23
 Key2: 23Test
 Packet 2 23[Encrypted data]


Purpose of folding a digest in half The Linux kernel's random driver generates randomness by hashing an entropy pool using SHA-1. From the driver's source, the SHA-1 hash is apparently folded in half before being returned:

/*
 * In case the hash function has some recognizable output
 * pattern, we fold it in half. Thus, we always feed back
 * twice as much data as we output.
 */
hash.w[0] ^= hash.w[3];
hash.w[1] ^= hash.w[4];
hash.w[2] ^= rol32(hash.w[2], 16);

The reasoning in the comment strikes me as a bit odd. Why would there be any expectation that SHA-1 would have a pattern in output, much less one where folding the hash in half would solve the issue? It looks to me like the kernel developers are attempting to design a worthless "hash" to try to solve some supposed problem with SHA-1. This behavior even goes back to 2003 (and possibly before), in kernel 2.4. Is there any possible advantage to this behavior, or is it wholly unnecessary?

Look at the rest of the code around it. The hash value gets used twice: once to feed back into the pool and once as an output. Ideally those two would be independent, but the requirement is that an attacker who sees the output is not be able to tell what went into the pool.

Another option would be to halve the hash, throw half of it back in and the other half out. However, in that case the data being fed back would be just 80 bits - short enough for a brute force attack without knowing the output. Hence the comment earlier in the file: "By mixing at least a SHA1 worth of hash data back, we make brute-forcing the feedback as hard as brute-forcing the hash."

So basically the XOR is used as a cheap one way function. Is it any better than taking just the first half and throwing both back in the pool? SHA-1 would have to be pretty broken for that to make any difference.

Then again, this code to fold in half is actually from a time when using SHA-1 was an option and MD5 the default (early-mid 90s, not sure exactly when). So distrusting the hash was not nearly as paranoid as it seems today. Later patches have left it in because it's "harmless".

I think that it's a belt and braces approach to using SHA-1.  You're right in that function has not yet been inverted directly, although collisions can now be made (with some effort).

There is also java.SecureRandom() though, which is Java's SUN CSPRNG implementation called SHA1PRNG.  It's based on a seed + counter fed through SHA-1, and it too only outputs 64 bits from the available 160 due to unspecified security concerns which I read somewhere. They don't fold in this case, they chuck the rest away.  I can't find that link now, but I have someone else's pseudo code of part of SHA1PRNG:-

I can't think of any other reason.  But to be honest, I'd probably do exactly the same if I was forced to use a state or pool for a TRNG.


Why is Poly1305 popular given its 'sudden death' properties? ECDSA has the undesirable property that if a key pair reuses a nonce in a signing operation, the cryptosystem experiences catastrophic failure in the form of private key leakage. I've heard this referred to as "sudden death" cryptography. Of course the PS3 misuse of ECDSA is probably the most widely publicised incident.

One advantage of DJB-advocated cryptosystems like Ed25519 is that they lack this weakness. The Ed25519 website states that "hash function collisions do not break this system."

A perfect implementation of ECDSA will be problem free, but since implementation flaws are inevitable, it seems preferable to use cryptography without huge exposed sharp edges.

This being the case, I am puzzled by the DJB's and other's advocacy for an authentication function that exhibits "sudden death" in the event of inadvertent nonce reuse.

Is the use of Poly1305 really informed only by performance? If so, why is this so crucial? The widespread use of e.g. HMAC suggests that MAC computation costs are tenable as they are and without pressing issue. I don't understand why Poly1305 is receiving such preference when it seems so dangerous. Can someone explain this?

At least in the case of NaCl, Poly1305's "sudden death" properties aren't much worse than XSalsa20's. With any stream cipher, if you reuse the same stream with two messages, then the XOR of the ciphertexts gives you the XOR of the plaintexts. So your security is already ruined by nonce reuse, whether or not you rely on Poly1305.

ECDSA based on NIST curves contain hard-coded numbers that the community find suspicious. In cryptography, the rule is to throw away the baby, the bath tube and the water when there is some doubt about chlorine origin.

DJB curve (the 2 variants ed25519 and c25519) is not based on hardcoded numbers. It is based on a modulus easy to use on standard computer architecture. The choice of c25519 is based on the fact that this curve is convenient for DH exchange, where coordinate Y is not needed. The choice of ed25519 is based on its convenience is signature scenarios, where point at infinity is not a concern in strongly unified addition formula.

SHA1 has magic numbers too, even if they are more or less vetted by the community.
Poly1305 has no such magic numbers.

Speed arguments depend on implementations and optimizations.

Implementations based on flat unconditional code are more likely to be bug-free.

Computation costs IS a concern in data centers where crypto computing requirements exploded over the last years, under the pressure for privacy and security.

The problem was not to solve existing problems at a higher level (like the reuse of nonce and salt in any crypto algorithm). The problem was to create crypto function which cannot be questionned.


RSA - Is $e = d$ a problem? I'm working on small RSA project in university.
At this moment I have done this:

An array of prime numbers is generated from selected range.
$p$ and $q$ selected randomly from this array
$n$ calculated
$\phi(n)$ calculated
$e$ calculated
$d$ calculated

What do you think about $e$ and $d$ in that case?

$p = 29$
$q = 53$
$n = 1537$
$\phi(n) = 1456$
$e = 545$
$d = 545$

It would be disastrous if an RSA key generation procedure had a sizable probability to end with $e=d$, because in that case, the public key reveals the private key, which must be secret from a security perspective.
But $e=d$ is a symptom of a larger problem lying in steps 1 and 2 of the key generation procedure: RSA can only be secure if $p$ and $q$ are selected in a way such that factoring $n$ is hard, and that means $p$ and $q$ should be large primes. The modern baseline is $n$ of $2048$ bits, that is $617$ decimal digits, not $4$ decimal digits. For this, $p$ and $q$ are chosen randomly among a sizable subset of primes of about $309$ digits. There are over about $10^{305}$ such primes, thus generating them all then picking within that is infeasible. The right procedure is to directly generate $p$ and $q$.
With $p$ and $q$ random primes this large, and a random choice of $e$ such that $\gcd(e,\phi(n))=1$ (or a random choice of primes $p$ and $q$ with the only dependency on $e$ that $\gcd(e,p-1)=1$ and $\gcd(e,q-1)=1$, as is common practice), it's infinitesimally improbable that $d=e$, or more generally that one or a few re-encryption(s) lead to decryption. See these questions on the cycling attack.

There are RSA key generation procedures in FIPS 186-4 appendix B.3. Ignore the proposed $1024$-bit key size, which is obsolete. The proposed $2048$ is the baseline, $3072$ increasingly common, extending to $4096$-bit not unreasonable. These procedures differ from those used in the question by several points including:

Generating large primes $p$ and $q$ unpredictably in a prescribed interval $[2^{(k-1)/2},2^{k/2}]$, where $k$ is the desired bit size of $n$ (e.g. $3072$)
Requiring odd $e$ with $2^{16}<e<2^{256}$ (the lower because that acts as a safeguard against poor choices of RSA padding, the higher for interoperability and to make some other poor choices impossible)
Using $d=e^{-1}\bmod\lambda(n)$ (where $\lambda$ is the Carmichael function) rather than $d=e^{-1}\bmod\phi(n)$. Both are mathematically fine, but using $\lambda$ insures generating the smallest positive private exponent $d$ working for a given $(n,e)$.
Requiring a minimum size of $d$ (much larger than $2^{256}$, which incidentally insures $d>e$), more as a safeguard against errors than out of mathematical necessity.

Although we commonly use (p-1)*(q-1) to calculate d, you can actually use lcm(p-1, q-1) [least common multiple] and get smaller values for e and d that work. Now 545 squared mod 1456 = 1, so yes the calculations are correct (if a bit weird). Try a smaller value for e, and you should values that make more sense.


Does RSA have two trapdoors? I watched some videos from Khan Academy explaining the algorithm for RSA encryption/decryption. They explained that there are two trapdoors, modular exponentiation being one and prime factorization being the other. Is this true though? As the videos went on it made it seem like prime factorization was what made the inverse of modular exponentiation difficult to solve. Did I misunderstand something, or is modular exponentiation just a naturally difficult problem to compute?

Defining RSA Problem as finding $m$, having $N,e,c$ where $c=m^e \mod N$ and $N=pq$, two unknown same-size prime numbers.

So far the best generic method we know to solve this is to factor $N$.

But there might be other methods, so far unknown, to compute the $e$-th root of $c$ and recovering $m$.

This is different from the discrete logarithm problem, where the exponent is secret. This is just computing an $e$-th root. We know how to compute roots modulo a prime, we don't know how to compute roots modulo a composite number of unknown factorization.

Note: for bad choices of m (i.e. without the use of padding) or $e$ or $d$ (the private exponent) there are practical attacks that recovers $m$ without factoring. For example the Weiner's or Coppersmith's attack. In particular the method of Coppersmith does compute $e$-th roots if $e$ and $m$ are small enough therefore it is not a generic method.

The RSA Problem is at least as easy as factoring. But there might be other, so far unknown, easier way to compute $e$-th roots without factoring.

It's because there's no known real way to calculate massive prime numbers quickly and effectively. I forget where I saw it but there is a picture of a chart showing how a computer can calculate the primes of the n value, but as they get massive it slows even the fastest computers down. So with no real formula for calculating primes it takes a while.


Creating Random Pad from XORed Sections of Pi If two strings of equal length from random offsets in Pi were XORed together, would this result in a cryptographically secure random number suitable for use in a one-time pad? If so, would this mean that using a secure low-bandwidth channel, you could bass three digits (two offsets and a length) to provide an arbitrarily long pad?

There's no benefit whatsoever to using XOR here. Pi is already believed to be Normal which means the stream of digits is indistinguishable from random in every base.

The offset into Pi functions as a key, for your system to be secure this key must be very large (e.g. several dozen decimal digits long) and chosen entirely at random, and it must not become known to anybody except the communication parties. With those constraints you should just use a stream cipher which is intended for this purpose.

If you just believe that "Nobody" would guess that your "three digits" are the key to a cipher based on Pi and so it's safe to just transmit the key to the other party you're relying on Security by Obscurity and might just as well use mirror writing or pig latin or something.


MIT says: mathematical theory behind encryption is wrong. What are the consequences? A friend shared with me the following link: Encryption is less secure than we thought

I'm not a security expert and could understand great part the article, except the section about noise, but what I haven't figured out is the impact of that research in real life.

What does it mean for mortals, in practice?

So the article is fluff, the details can be found in the linked paper.  The just of it is a refutation of the following assertion: if you have a set of symbols chosen with identical independent distributions and subject to some kind of coding, the result can be approximated as a uniform distribution.

The paper asserts, with a few citations to some examples, that this is a common cryptographic assumption. It is, as far as I can tell from reading the literature and talking to other practitioners, not a common assumption at all. In fact, in standard encryption systems, we assume that the plaintext is chosen with a known distribution that can be arbitrary(indeed, attacker chosen), and keys are chosen randomly.

In practice, keys are not chosen randomly, they are chosen using cryptographically secure random number generators. Those can fail, but not in the way the paper is talking about.

Certain papers, such as maybe the cited ones about biometrics and  passwords, might make this erroneous assumption, but it's not common and certainly  doesn't relate to what most non-practitioners would consider "encryption."

Moreover, it appears that you still can't make guesses about messages in polynomial time with this technique, you can just make them in faster exponential time. It depends highly on how the assumption was used if this maters in practice. Not having read the papers which do make this assumption, I can't say for sure, but if doing this breaks those systems in a practical sense, the schemes likely had other issues.

A better title for the article is: a few cryptographers made some dumb mistakes. Mistakes neither pervasive or of massive consequence.

Use a truly random password.  The summary wasn't very good, but basically it seemed to indicate that certain cases result in faster failures because of low entropy input, which basically falls in to the realm of proving what we've known for years.  I don't really see how this is big news.  It's just a (maybe) better way of modeling the reduction of entropy due to a lack of true randomness in any aspect of the system.  I don't see any immediately practical implication of the paper, at least from the information presented in the summary.