If its possible to derive the public key from a private key, why can't we go in reverse? I'm looking at source code for BitcoinJ that derives a public key from the private key.

  /**
     * Create the public key from the private key
     *
     * @param       privKey             Private key
     * @param       compressed          TRUE to generate a compressed public key
     * @return                          Public key
     */
    private byte[] pubKeyFromPrivKey(BigInteger privKey, boolean compressed) {
        ECPoint point = ecParams.getG().multiply(privKey);
        return point.getEncoded(compressed);
    }

Since "G" is known, and published for each given curve, what prevents someone from dividing (or multiple consecutive subtractions) to determine the private key?

If possible, would you explain it in layman's terms, and also provide additional concepts I can research the relevant background.

Concerning your notation problem, yes that is kind of an issue. First, elliptic curves in cryptography are usually noted in additive notation. That's why the function call is called "multiply" and is not just a "simple multiplication" but in practice it uses the same principle as exponentiation for "normal numbers" (implemented mostly as "square and multiply", or in additive notation "double and add").

In the basic finite fields, however, people use mostly multiplicative notation to imply, that the DLOG problem is hard, because the equivalent problem based on the addition of numbers is quite easy (given numbers $a$ and $b$, everyone can calculate $a\cdot b$).

To answer your problem with the understanding: In elliptic curves, the "division" operation is not possible (well, computationally hard). This is based on the fact, that in elliptic curves we have only one group structure and we have to work with only this. Finite fields, however, offer us two group structures and they are linked by the distributive property, which in return makes the Diffie-Hellman problem easy for the additive group structure.

You can absolutely derive the private key from the public key. Just keep subtracting the base point from the public key until you get to the base point. And keep count of how many times you subtracted. You could get extremely lucky on your first try. But that isn't likely. On average, with current computer technologies, it would take thousands of years.


Given an elliptic curve, how do I calculate the order of the points manually, when we don't know about the curve's points? So basically all I can do is

use Lagrange's Theorem and figure which factors of the group order are in line, then
start trying each of these using the Double-and-Add-Algorithm until I get $\mathcal{O}$?

This takes forever if I do it by hand. Is there any easier way to find the order of all points? or find all the points on the curve?

Okay after some research: There is no shortcut. If you do it manually you need to proceed as suggested above. Realistically this is possible only for very small curves because of the complexity.

Given the Elliptic curve $E:y^2= x^3 + 2x + 2  \pmod {17}, \#P=19$

We can get all the points: by hands and by Python programming

1. For small number, we calculate it by hand. The procedure is:

1.1 For every $x$, we calculate  $x^3 + 2x + 2  \pmod {17}$, the list is:

$x^3 + 2x + 2  \pmod {17}$　　　　　　　　　　　　　　　　　　$x$

2　　　　　　　　　　　　　　　　　　　　　　　　　　　　[0, 7, 10]
3　　　　　　　　　　　　　　　　　　　　　　　　　　　　[8, 12, 14]
5　　　　　　　　　　　　　　　　　　　　　　　　　　　　[1]
6　　　　　　　　　　　　　　　　　　　　　　　　　　　　[4]
7　　　　　　　　　　　　　　　　　　　　　　　　　　　　[15]
9　　　　　　　　　　　　　　　　　　　　　　　　　　　　[6]
12　　　　　　　　　　　　　　　　　　　　　　　　　　　　[11]
14　　　　　　　　　　　　　　　　　　　　　　　　　　　　[2]
15　　　　　　　　　　　　　　　　　　　　　　　　　　　　[13]
16　　　　　　　　　　　　　　　　　　　　　　　　　　　　[16]

1.2 Similarly, for every $y$, we calculate  $y^2  \pmod {17}$ , the list is:

$y^2  \pmod {17}$　　　　　　　　　　　　　　　　　　　　　　$y$

1　　　　　　　　　　　　　　　　　　　　　　　　　　　　[1, 16]
2　　　　　　　　　　　　　　　　　　　　　　　　　　　　[6, 11]
4　　　　　　　　　　　　　　　　　　　　　　　　　　　　[2, 15]
8　　　　　　　　　　　　　　　　　　　　　　　　　　　　[5, 12]
9　　　　　　　　　　　　　　　　　　　　　　　　　　　　[3, 14]
13　　　　　　　　　　　　　　　　　　　　　　　　　　　　[8, 9]
15　　　　　　　　　　　　　　　　　　　　　　　　　　　　[7, 10]
16　　　　　　　　　　　　　　　　　　　　　　　　　　　　[4, 13]

1.3. Find the sets of intersection with the same value of module, and calculate the product of the two sets.

For example, regarding the same module $1$, we calculate the product.
$[3, 5, 9] \cdot [1, 16]$, the result is:
$(3,1),(3,16),(5,1),(5,16),(9,1),(9,16)$

1.4. For all the same module, we get the total result(18 points):

$(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13) $

By adding the implicit infinity point $\mathcal{O}$, the $\#P=18+1=19$

2. We can use brute force algorithm with python program to find all the points on one curve.

Given the Elliptic curve $E:y^2= x^3 + 2x + 2  \pmod {17}, \#P=19$

2.1.  We can get all the points by programming.

# -*- coding:UTF-8

import itertools

# y^2 = x^3 + 2x + 2 (mod 17)
p=17
a=2
b=2

xlable = dict()
ylable = dict()

# for all the number x, get the module (x^3 + ax + b) % p
def lablex(x):
   xlable.setdefault((x**3+a*x+b)%p, []).append(x)

# for all the number y, get the module (y^2) % p
def labley(y):
   ylable.setdefault((y**2)%p, []).append(y)

# calculate all the number
for num in range(0,p):
   lablex(num)
   labley(num)

# get all the points an length
intersect = []
for item in xlable.keys():
   if ylable.has_key(item):
       tmp = list(itertools.product(xlable[item], ylable[item]))
       intersect = intersect + tmp;
print "points:", sorted(intersect)
print "length:", len(intersect)

2.2. Run this program, we can get the result:

points: [(0, 6), (0, 11), (3, 1), (3, 16), (5, 1), (5, 16), (6, 3), (6, 14), (7, 6), (7, 11), (9, 1), (9, 16), (10, 6), (10, 11), (13, 7), (13, 10), (16, 4), (16, 13)]
length: 18

By adding the implicit infinity point $\mathcal{O}$,  the $\#P=18+1=19$

2.3. For another  Elliptic curve $E:y^2= x^3+x  \pmod {257}, \#P=256$

We can also get the correct result.

points: [(0, 0), (1, 60), (1, 197), (3, 95), (3, 162), (4, 117), (4, 140), (6, 42), (6, 215), (10, 53), (10, 204), (11, 91), (11, 166), (12, 55), (12, 202), (15, 7), (15, 250), (16, 0), (18, 14), (18, 243), (19, 14), (19, 243), (21, 95), (21, 162), (22, 90), (22, 167), (23, 25), (23, 232), (24, 22), (24, 235), (27, 101), (27, 156), (28, 69), (28, 188), (34, 70), (34, 187), (35, 48), (35, 209), (37, 33), (37, 224), (38, 13), (38, 244), (39, 48), (39, 209), (42, 63), (42, 194), (43, 44), (43, 213), (46, 39), (46, 218), (47, 82), (47, 175), (49, 121), (49, 136), (52, 9), (52, 248), (54, 100), (54, 157), (56, 107), (56, 150), (59, 98), (59, 159), (61, 25), (61, 232), (63, 7), (63, 250), (64, 117), (64, 140), (66, 39), (66, 218), (67, 59), (67, 198), (68, 73), (68, 184), (70, 80), (70, 177), (73, 121), (73, 136), (74, 3), (74, 254), (75, 124), (75, 133), (77, 101), (77, 156), (78, 112), (78, 145), (80, 81), (80, 176), (81, 118), (81, 139), (82, 106), (82, 151), (84, 114), (84, 143), (86, 18), (86, 239), (88, 32), (88, 225), (92, 29), (92, 228), (95, 115), (95, 142), (99, 123), (99, 134), (100, 65), (100, 192), (101, 54), (101, 203), (102, 97), (102, 160), (104, 74), (104, 183), (106, 21), (106, 236), (107, 51), (107, 206), (112, 110), (112, 147), (115, 8), (115, 249), (119, 30), (119, 227), (120, 56), (120, 201), (122, 120), (122, 137), (125, 43), (125, 214), (132, 83), (132, 174), (135, 121), (135, 136), (137, 125), (137, 132), (138, 34), (138, 223), (142, 128), (142, 129), (145, 39), (145, 218), (150, 45), (150, 212), (151, 79), (151, 178), (153, 101), (153, 156), (155, 10), (155, 247), (156, 93), (156, 164), (157, 12), (157, 245), (158, 88), (158, 169), (162, 41), (162, 216), (165, 50), (165, 207), (169, 2), (169, 255), (171, 31), (171, 226), (173, 25), (173, 232), (175, 103), (175, 154), (176, 89), (176, 168), (177, 11), (177, 246), (179, 7), (179, 250), (180, 74), (180, 183), (182, 72), (182, 185), (183, 48), (183, 209), (184, 120), (184, 137), (187, 5), (187, 252), (189, 117), (189, 140), (190, 84), (190, 173), (191, 110), (191, 147), (193, 73), (193, 184), (194, 112), (194, 145), (196, 114), (196, 143), (198, 26), (198, 231), (201, 87), (201, 170), (203, 58), (203, 199), (205, 113), (205, 144), (208, 120), (208, 137), (210, 27), (210, 230), (211, 110), (211, 147), (214, 67), (214, 190), (215, 20), (215, 237), (218, 3), (218, 254), (219, 49), (219, 208), (220, 14), (220, 243), (222, 3), (222, 254), (223, 92), (223, 165), (229, 76), (229, 181), (230, 74), (230, 183), (233, 95), (233, 162), (234, 114), (234, 143), (235, 102), (235, 155), (236, 22), (236, 235), (238, 33), (238, 224), (239, 33), (239, 224), (241, 0), (242, 112), (242, 145), (245, 109), (245, 148), (246, 86), (246, 171), (247, 77), (247, 180), (251, 99), (251, 158), (253, 73), (253, 184), (254, 22), (254, 235), (256, 68), (256, 189)]
length: 255

By adding the infinity point $\mathcal{O}$, the $\#P=255+1=256$


Can you help me prove perfect secrecy? I'm actually new to cryptography and a friend of mine requested that I should read the Katz and Lindell book – “introduction to modern cryptography”.
As I read the book I found it very interesting but I'm finding some problems answering a few questions from the book,(for someone new like me I managed to to answer section 1 and almost section 2), but enough talk I'm getting straight to the questions:
First of all, I needed to prove witch of these two assumptions is perfectly secret :

The message space is $M = \{m \in \{0, 1\}^l \text{ | the last bit of }m \text{ is }0\}$.
Gen chooses a uniform key from $\{0, 1\}^{l−1}$. $Enc_k(m)$ returns ciphertext
$m \oplus (k || 0)$, and $Dec_k(c)$ returns $c \oplus (k || 0)$.

The message space is $M = \{0,..., 4\}$. Algorithm Gen chooses
a uniform key from the key space $\{0,..., 5\}$. $Enc_k(m)$ returns
$[(k + m) \bmod 5]$, and $Dec_k(c)$ returns $[(c − k) \bmod 5]$.

Suppose that we have $\pi(Gen,Enc,Dec)$.
For the first one I guess that I answered it but I need you guys to correct me since I'm not sur if my method is true or not :

$M = \{0, 1\}^l$
$n$ and $k = \{0, 1\}^{l-1}$
with $Enc_k(m)$ outputting $c = m_{[1,ℓ-1]} \oplus (k||0)$, i.e the xor of the first $(l-1)$ bits of $m$ with the key $k$.
The decryption outputs $Dec_k(c)$ as $c \oplus (k||0)$ concatenated with a random 1 bit string (0 on each of the cases $Enc$ & $Dec$).
This scheme satisfies the $2^{−1}$ property that
$Pr[Dec(Enc(m)) = m] \geq 2^{-1}$ for every $m$, which means that in the first assumption the scheme is perfectly secure.

For the second case I have no idea how to put that proof on the line.

It would be good if you revisited the definition of perfect secrecy in the book. What you are proving for the first candidate scheme is a correctness property, not a security property (in general), and not perfect secrecy in particular.

Informally, what you are proving is that encrypting and then decrypting will preserve the original message. What you need to prove is that guessing $m$ knowing $c$ (where $c=Enc_k(m)$) the is as hard as guessing $m$ without seeing $c$.

As a general strategy, a good way to prove something secure is to base your proof on similar, already proven constructions. Scheme 1 is very similar to one-time pad, so the proof should be adaptable.

For proving something insecure, it's often simpler to describe a specific attack or even a counterexample. Scheme 2 for example is not perfectly secret. Since you are given small, concrete values, you can try and work out some example encryptions using pen & paper to see if something's wrong.

I had some quite similar problems for homework recently, what helped me through was considering special cases. For the first one note that when $\mathcal{C}=\{0,1\}^l$ $$Pr[M=0^l|C=1^1]=0 \wedge Pr[M=0^l]=\dfrac{1}{2^l}$$ so the scheme is not perfectly secure. As for the second part, check what happens for $m=c=0$. Cheers!

Edit 1: Now $\mathcal{C}\neq\mathcal{M}$. My bad.


Does character encoding change entropy? This is a question I've been wondering for a while.

Technically these two strings have the same entropy I believe:

fkfnajkfkg%gsddg£5ER£%££££

0110011001101011011001100110111001100001011010100110101101100110011010110110011100100101011001110111001101100100011001000110011111000010101000110011010101000101010100101100001010100011001001011100001010100011110000101010001111000010101000111100001010100011

both 256bits...

My question is, does character encoding affect entropy?

If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

If 256bits is good as an AES key, it's also good as a password right?

I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

Blake2B(password) = 7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

Blake2B(fkfnajkfkg%gsddg£5ER£%££££) = 03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

Are,

7c863950ac93c93692995e4732ce1e1466ad74a775352ffbaaf2a4a4ce9b549d0b414a1f3150452be6c7c72c694a7cb46f76452917298d33e67611f0a42addb8

and

03e7415fa598e9062cfd9e3cd269ca618b38b3543501e197b6c095b8749d782234e82779a2e4b489fd9c3b002734763ee3b867835e1a2232a37bf89ef8606d09

the same entropy?

If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

Technically these two strings have the same entropy I believe:

We cannot tell how much entropy is in a string by looking at it, as it depends on how it is generated and if the values cannot be predicted by other means. For instance, you just posted these strings on this site, so they would not contain (almost) no entropy when used as keys.

Your strings just represents a bit string, possibly of the same size - as you presume, depending on the actual encoding (I don't know the encoding used for the first string, and I can only assume binary digits for the second string). And those bits may contain entropy.

  My question is, does character encoding affect entropy?

No, it doesn't as the character encoding is just about the representation of the bits, not the actual value of the bits. The entropy is present in the value of the bits.

  If generated at random, do both the ASCII and binary strings have the same entropy as passwords?

Yes, assuming that the alphabet is not larger than expected.

  If 256bits is good as an AES key, it's also good as a password right?

No, because normal humans cannot remember such large strings. You could store them in a password manager though, and then 256 bits of entropy is plenty, if not overkill. Generally we don't need password sizes or keys over 128 bits - as long as quantum computers don't come of age anyway.

  I guess a similar question is does hashing a 'weak' password give a lower entropy string than a 'strong' password, consider this:

No, now the value of the bits of the input string contain less entropy, so this isn't comparable at all. The entropy is not expanded by the password hashing algorithm, so the earlier hash contains less entropy than the latter hash.

  If I hadn't told you the first was the hash of password and the second the hash of fkfnajkfkg%gsddg£5ER£%££££, would it change your view?

No, because a dictionary attack would almost immediately find the first hash.

  I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

That depends. Let's assume that all the security is in the password or key. In that case we work with Kerckhoffs principle, and we assume that we know how the password is encoded. In that case there is no difference.

Of course, a real world attacker may not work that way. You may use your password for a generic store, and an attacker may not try your particular encoding.

Most humans are terribly bad at remembering 256 ones and zeros. There may be other technical difficulties in entering such a long string of characters as well (screen space, remembering where you are in the string, stealing clipboard contents etc. etc.).

Yes and no. The strings certainly both have the same Kolmogorov complexity.

Some here loosely generalise the cryptographic definition of entropy as Kolomogorov complexity = entropy. That's not quite correct and confusing.  Kolmogorov complexity is the thing that cryptographers are interested in when assessing the strength of passwords and seeds.  Entropy (information) is measured a-priori of knowing anything other than what you measure at any specific point. Entropy (information) is very much a localised metric and can thus be transformed.

So clearly your two sequences must have differing (information) entropies as they're different lengths due to the encoding.  Philosophically and semantically though they're identical. So the effort to brute force either is identical too.

As to then:-

  I also suppose there is a difference between brute forcing a password which is 256bits, and one which is 256 ASCII 1's or 0's, which would be more than 256bit.

No, but it might take more RAM/die estate to hold the candidates. The entropy rate of the former is 8 bits/byte, whilst the latter is 1 bit/byte. It may be worthwhile looking at What is the most secure encryption algorithm that keeps the entropy the same or even lowers it?. And also consider the difference between a cryptographic "key" like those above, and a "password" which is like "123456".


PRP, PRF and modular arithmetic Are there any arithmetic or mathematical functions that can be used as PRPs or PRFs ?  Since, Conventional block ciphers like AES are that are proven to be good PRPs are not based on mathematics but on other principles like confusion and diffusion etc.

Do you want DDH/RSA-based PRFs? If so, we have them and I will answer. –  xagawa

  @xagawa Yes, I want that :-) –  Dingo13

I list the PRFs based on the number-theoretical assumptions.
They are ``arithmetic or mathematical function.''
You can use the Feistel network to obtain (S)PRPs from PRFs in theory.

From the DDH assumption

The Naor-Reingold Pseudorandom Function is a PRF based on the DDH assumption.
Let $\mathbb{G}$ be a finite group of order prime $q$ with a generator $g$,
on which the DDH problem is hard.
Let $\{0,1\}^\ell$ be a domain.
The function is defined as
$$\mathrm{PRF_{NR}}(k, x) = g^{a_0 \prod_{i=1}^{\ell} a_i^{x_i}},$$
where $k = (a_0,a_1\dots,a_{\ell}) \in \mathbb{Z}_q^{\ell}$.
For the proof, see the original article in J. ACM.

Lewko and Waters generalized the NR PRFs in CCS 2009 (and ePrint 2009/486).
Their PRFs are based on the decisional linear assumption (and its weaker variants).

Most efficient one

Under stronger assumptions such as the DHI assumption,
 we have a cute PRF, say,
the Dodis-Yampolskiy PRF proposed as
Verifiable Random Function (VRF).

Let $\{0,1\}^{\ell}$ be the domain of PRF.
Suppose that $2^{\ell}$ is a polynoimal of the security parameter.
The DY PRF is defined on a symmetric bilinear group as follows:
$$\mathrm{PRF}_{DY}(k,x) = e(g,g)^{1/(x+k)},$$
where $k \in \mathbb{Z}_q$.

From the factoring assumption

This is a classical result obtained by a combining the Blum-Blum-Shub PRG and the Goldreich-Goldwasser-Micali PRF from any PRG.
Naor, Reingold, and Rosen improved efficiency of factoring-based PRFs.
See the original article available at ECCC TR 2001-064,

From the hardness of lattice problems

Nowadays, the lattice problems are often employed to construct cryptogrphic primitives.
You can find the PRFs from lattices in
Banerjee, Peikert, and Rosen (EUROCRYPT 2012),
Alwen, Krenn, Pietrzak, and Wichs (CRYPTO 2013),
and Banerjee and Peikert (ePrint 2014/074).

No. Conceptually , not so strongly close but similar ones that would come closer is $k$-wise Independent Distributions/Functions .


Calculating 3DES Key Check Value (KCV) I am trying to verify a Triple DES Key Component generated by PC Crypto.
The key portion is:

E6F1081FEA4C402CC192B65DE367EC3E

and the KCV value that should be returned is:

212CF915

In theory, it should be calculated as: encryption of binary 0's with the key portion with 3DES.

I have been trying the following link, but the calculation doesn't work.
http://tripledes.online-domain-tools.com/

I used the following parametrization on the online tool.

Could anyone confirm that the calculation is performed as I mentioned?

Three problems here:

The online tool used expects a 24-byte (48 hex-character) key; thus you should enter E6F1081FEA4C402CC192B65DE367EC3EE6F1081FEA4C402C as the key, duplicating the first 8 bytes; this is the customary way to extend a two-block triple DES key of 16 bytes to a three-block triple DES key of 24 bytes.
You gave 16 bytes (32 hex chars) as input, which is twice as many bytes as required; this doesn't affect the computation of the KCV though.
The KCV value is supposed to be the first 3 bytes (6 hex chars) of the result, not 4 bytes (8 hex chars).

When this is fixed, the KCV 212cf9 is correctly obtained using the tool.

Note: it is a bad idea to use an online tool in order to check a real key, just like it is a bad idea to use an online RNG to generate a real key.

Key:           E6F1081FEA4C402CC192B65DE367EC3E
 Algorithm:     3DES ECB
 Crypto operation:  Decoding
 Data:          212CF915
 Padding Method:    None

Decoded data:      EBB7EC7B4CC5C804
 DES operations count:  3

[2016-10-12 12:58:39] DEA Keys: Key parity enforcement finished

Key:           E6F1081FEA4C402CC192B65DE367EC3E
 Key length:        32
 Parity enforced:   Even
 New key:       E7F0091EEB4D412DC093B75CE266ED3F
 KCV:           212CF9

Key:           E6F1081FEA4C402CC192B65DE367EC3E
 Algorithm:     3DES ECB
 Crypto operation:  Encryption
 Data:          212CF9
 Padding Method:    Zeros

Encrypted data:    13894FA653595256
 DES operations count:  3

[2016-10-12 13:02:09]
 DES/3DES operation finished

Key:           E6F1081FEA4C402CC192B65DE367EC3E
 Algorithm:     3DES ECB
 Crypto operation:  Encryption
 Data:          212CF9
 Padding Method:    None

Encrypted data:    4242424242420000
 DES operations count:  0


Choosing which is public vs private key When I calculate two RSA keys, what if anything, would make any difference which I call the public vs which I call the private key?

In any RSA-type cryptosystem, a public key necessarily has a modulus $n$, and sometimes has an exponent $e$ if it's not prescribed by the cryptosystem.  Sensible cryptosystems like RSA-KEM can prescribe $e = 3$, but some defective standards, based on mistakes like RSAES-PKCS1-v1_5, may require $e$ to be $e = 65537$ or larger and may allow $e$ to vary.

A private key can come in any of several forms:

the factors $p$ and $q$ of $n = pq$
a private exponent $d$, which solves $e \cdot d \equiv 1 \pmod{\lambda(n)}$
Chinese remainder theorem exponents $d_p \equiv d \pmod{p - 1}$ and $d_q \equiv d \pmod{q - 1})$

Any of these forms of the private key is equivalent, given knowledge of $n$: from $p$ and $q$ you can compute $\lambda(n) = \operatorname{lcm}(p - 1, q - 1)$ and solve $e d \equiv 1 \pmod{\lambda(n)}$ with the extended Euclidean algorithm; from $d$ you can recover a multiple $e \cdot d - 1$ of $\lambda(n)$ and without much additional difficulty proceed to factor $n$; etc.  Often, as in, e.g., OpenSSL, many redundant parts of the private key are stored together to speed up the computation.

The main question, then, is: Are the public exponent $e$ and the private exponent $d$ interchangeable?  And the answer is: No.

In Rivest, Shamir, and Adleman's seminal paper, the proposed method was to choose $d$ at random to be coprime with $\phi(n) = (p - 1)(q - 1)$ and then to derive $e$ from $d$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  One could do it the other way around: choose $e$ at random to be coprime with $\phi(n)$, and then to derive $d$ from $e$ by solving $ed \equiv 1 \pmod{\phi(n)}$.  So, if you were stuck in 1978, it might look like the roles of the two exponents are interchangeable—but if you were stuck in 1978, your encryption scheme would also be trivially breakable,* so maybe you don't want to stay in 1978.

The main cost for a user of RSA is computing modular exponentiation, which for exponent $x$ costs $\lfloor\log_2 x\rfloor$ squarings and $H(x) - 1$ multiplications, where $H$ is Hamming weight.  The most efficient exponent is 3—but you can only do this for the public exponent!  If you always picked the private exponent $d = 3$, you would still have to publish $e$ in order for anyone to encrypt messages—but if you did that, then armed with knowledge of $e$ and $d$ I could find $\lambda(n)$ and factor $n$ and break the whole cryptosystem!

‘OK, fine,’ you say, ‘so $d = 3$ is no good, but what if I just picked $d$ to be small to speed up decryption?’  As it happens, if $d$ is merely smaller than about $\sqrt[4] n$, I can use Wiener's attack or a variant thereof to recover it!  It is therefore crucial that the private exponent $d$ be near uniformly distributed in the whole possible space, which is effectively the case even if you choose the public exponent $e$ to always be something small like 3 or 65537.

Thus while it is perfectly safe in sensible RSA-type cryptosystems to always use $e = 3$, it is dangerous to choose even moderately small $d$; the exponents are very much not interchangeable.

P.S.  You may be tempted, by the seductive symmetry of the equations $c = m^e \bmod n$ and $m = c^d \bmod n$, to treat encryption and signature as interchangeable too.  Don't do it!  It's a trap!  If you try to shoehorn a message into this shape, you'll likely end up shooting yourself in the foot; there's much more to encryption and much more to signature, and beyond the use of exponentiation they bear very little resemblance—and if you naively try to combine the two with the same keys you will probably shoot yourself in the other foot too.  At that point, you'd better hope you're an octopus.

* They recommend what is effectively RSA-ECB for encryption, and a trivially forgeable hashless signature scheme.  The first secure signature scheme by modern standards—assuming suitably scaled parameters—wasn't published until a year later by Rabin in 1979, using the qualitatively different exponent $e = 2$, and the first secure encryption scheme by modern standards wasn't published until some time after that.

With the secret key you can decrypt and actually you can reconstruct the public key. Knowing the secret key you can decrypt messages, so you want to keep that key confidential. On the other hand knowing the public key you can encrypt messages.


Is there a client-side program to cryptography a HTML page and decode if correct password is writen? I want to know if there is an easy way to do this:

create a complete HTML page
cryptography the text content (image is not important)
ask user some password
check the password with a cryptographed password if(hash(userPassword)==hasedPassword)) return true;
if the password is correct it will decode it and show the content.

All this in user-side, not server-side. Because this I will use javascript.

Is there any good implementation?

If you put the text content of the webpage encrypted into HTML5 local storage, IndexedDB or embedded as a hex/base64 string in the web page, then you you could try something like TripleSec which would take your password, run a PBKDF and decrypt the content.

Or you can use one of the many JavaScript libraries CryptoJS, SJCL etc and do it yourself manually.

You should run the code as a local .html file on the filesystem or in a browser extension. Don't make the mistake of running the JavaScript code served up from the server because your security would only be as strong as the HTTP/HTTPS connection and vulnerable to MITM. Even HTTPS is not secure against some attackers.

If you're doing this entirely client-side, it's trivial for someone to bypass it. You can't really use the user's computer to keep something from them. That's the problem DRM tries to solve, and even with the full cooperation of the OS to keep things from the user it doesn't work perfectly. Javascript can't do that at all; you need to do encryption on the server side to keep the user from bypassing it.


Some doubts about GnuPG I've reading on GPG since yesterday and I have a doubt: the whole system of double key encryption does make sense but it looks to me like either way you are compromising something in terms of security.

If someone sends me an encrypted file using GPG and he/she wants to make sure that I'm the only one able to decrypt it then he/she will encrypt that file using my public key. Now, the only way to decrypt it is to use my private key, which supposedly I'm the only one in the world to have it. So far, so good.

However, if we also want to make sure that there are no forgers and that we're actually exchanging files between us (issue 1) then we would need to encrypt files using each one their own private key. This requires us to share our public keys. But here we go, another problem (issue 2): what if I published my public key on a website/blog/etc. some time ago and I had forgot about it? What if an intruder is able to intercept such messages and by using the public key (that he/she found online) is now able to decrypt files?

The way I see it you have to compromise, and you can't really mitigate 100% both issue 1 and 2. Did I misunderstood something about GPG?

At this point, why not simply try to rely on a 7zip encryption and use a (moderately complicated) passphrase that you both know?

Thanks!

You cannot encrypt a file with a private key. With RSA, that's not because of any technical obstacle (with other schemes private keys literally are not valid inputs to the encryption function), but because private keys are designated as "private" and using them in an encryption operation compromises the security of that message. To prove you wrote the message, you don't encrypt it with your private key.

What you do do is sign the message. Signatures take a private key; best practices are to use a different keypair for signatures than for encryption (a default GPG "keypair" is really at two keypairs; there's a master keypair that's tied to your identity which is used only for signing, and a different subordinate keypair which is signed with the master keypair and which is used only for encryption). If you use different keys for signing and encryption, there are no issues with compromising your encryption.

Signing with RSA is not "encrypt with the private key." It has a passing resemblance to that (as the primitive used for encryption, the one for signing, the one for decryption, and the one for verification are all the same operation with different inputs and outputs) but it is a conceptually distinct algorithm which is designed not to let someone with the signature recover the message.

An RSA signature is created by creating a preimage-resistant hash of the message, doing various operations (known as padding) to the hash value to increase security, and passing it through the signature primitive (raising it to the power of the private exponent modulo $n$). In the more modern signature padding algorithm (PSS), the hash of the message is itself not recoverable, because it is combined with a random salt and passed through another preimage-resistant hash, and that is part of what's passed to the signature primitive (the other part is the salt, obfuscated using the hash of the hash+salt). In the older system (PKCS 1.5 padding), the hash could be directly recovered, but as it's preimage-resistant that doesn't give much help to an attacker looking for the message. An attacker in either case can test whether a given message was the one sent, but they can't find the message if they don't already have a candidate message.

Yes,

You totally got it wrong.

The idea if assymmetric crypto is quite simple. Everything you encrypt with one key can only be decrypt by the other. For the two key's it makes no difference which to use as private or public.

So if your public key is out there. A message encrypted with your public key can only be read by you. That's for the confidential if the message.

To prove who wad the sender if the message. You normally sign the message with your private key. This can than only be decrypt with your public key. What show's that you are the sender.


Is there a simple hash function that one can compute without a computer? I am looking for a hash function that is computable by hand (in reasonable time). The function should be at least a little bit secure: There should be no trivial way to find a collision (by hand). For instance, a simple cross-sum is not meeting this criteria since one can easily construct a number with the same hash than another.

Is there a (simple) function? I am interested in this for a presentation about commitment schemes in my CS class at school.

Well, depending on what's reasonable and what you can compute reliably by hand, you MIGHT be able to compute modular exponents in a moderate-size group (like $Z_n$ for moderate $n$).  Exponentiation via repeated squaring is doable I think.

Probably more practical would be a MD5-like ad hoc confusion-diffusion primitive.  You'd need to make the input large enough to make exhaustive search impractical by hand (32 bits should do it I would think?) and then make a round-function that was simple enough to compute by hand but had empirically-good collision-resistance.  Finally apply Merkle-Damgaard for a "few" rounds.

I would expect this to work reasonable well with a random crypto classmate.  If you're playing against Adi Shamir, you're probably screwed.

Edit: For in-person commitment schemes, you can get rid of hash functions altogether.  Just write a string of random bits on a folded paper and hand it to your partner to commit those bits.  But the more interesting scenario is doing this through a prison wall, over a phone, or over the internet... then you really need something mathematical.

Let's take the prison-wall example: you want to commit to another inmate some integer $x$ and you have no computational resources but can communicate with tapping (no paper).  Here's what I would do: pick a 64-bit number $x$ that you want to commit.  Make sure you can't factor it (it might be prime, but verifying primality is going to be tedious by hand).  Then choose another, larger, 64-bit number $y$ that is also hard to factor by hand.

Now compute $p=xy$ (easy) and send $p$ to your buddy.  If $x$ and $y$ were both hard to factor, $p$ is as well, so he can't extract $x$ or $y$ from $p$.  Now for the reveal, you send $x$ and $y$; he verifies that $p = xy$ and that $x$ is the smaller integer.

It's important that both are 64-bits (or both the same size) to prevent you from changing to $x'$ after the commit where $p = x' (k y)$.  This doesn't happen if $x$ and $y$ are prime, of course, but large primes aren't easy to generate by hand.

DISCLAIMER: this is NOT a mathematical/cryptographic hash function, but it is a one-way commitment scheme that does have SOME cryptographic attributes (pre-image resitasnce, collision-resistance):

Write your text in a piece of paper, sign it, and tear the paper,
ensuring the tear splits the text in 2.  Then hand over one half to the other party.

To verify the "hash", you need both halfs, and check that they match.  It is ultimately secure, at the molecular level.  Of course it is not flexible, nor extendable, but it may well serve as an example for a CS lesson on commitment schemes.


How to generate whitebox AES decryption algorithm and code, with existing WB-AES encryption code? I can find several whitebox AES 128 implementations on Github, such as wbaes-1, wbaes-2, wbaes-3, etc. All of them are developed based on WB AES encryption. Ideally, most implementations include two parts:

(1). Table_Generator.c  (or .cpp, .h ...). Input: 16-byte key; Output: a big lookup table (e.g., table.h), where the key information is already hidden in this lookup table

(2). AES_Encrypt.c. Input: plain text & table generated from (1); Output: cipher text

But I need decryption implementation as well.

First, let me confirm one basic question:

Encryption table & decryption table are generated separately, using one same key (e.g., 16 byte key for AES128)? Correct? which means there are two table generation algorithms (and hence two separate lookup tables) - one encryption, one for decryption.

Then, the main questions:

What are the important steps to modify an WB encryption project into
a WB decryption project?
Is there any WB AES decryption implementation for me to read?

Encryption table & decryption table are generated separately, using one same key (e.g., 16 byte key for AES128)? Correct? which means there are two table generation algorithms (and hence two separate lookup tables) - one encryption, one for decryption.

yes, this is correct. you need two different sets of tables to implement the encryption and the decryption algorithm. Both set are generated using, of course, the same secret AES key.

  What are the important steps to modify an WB encryption project into a WB decryption project?

To implement the AES decryption, one should undo all operation one-by-one doing the inverse: you could, therefore, rewrite the table generator algorithm following this logic and then writing the corresponding decryption function where the round structure is inversed.
Otherwise one can notice that decryption can be implemented using the same round structure as encryption but with a slightly modified key schedule (and the operations replaced by their inverses).
I suggest using this second way to implement decryption, as you only need to change the key schedule function and the rest of the implementation stays the same.

EDIT: more details are available on the AES standard publication at Section 5.3.5 where the Equivalent Inverse Cipher is described.

  Is there any WB AES decryption implementation for me to read?

if I remember correctly, the following implementation contains both encryption and decryption direction.
You can also read the very good tutorial by James A. Muir (pdf)

Encryption and decryption differ mostly in these two steps:

The S-Box for the SubBytes-step is inverted, so if e.g. 0x00 is mapped to 0x63 in encryption, in decryption 0x63 is mapped to 0x00 (see https://en.wikipedia.org/wiki/Rijndael_S-box).
The MixColumns-step. Here the values to mix the columns are different (inverted again, see https://en.wikipedia.org/wiki/Rijndael_MixColumns).

To get around this, you might simply use AES in counter-mode. This way, encryption and decryption become the exact same operation and you can simply use the encryption implementations you found for both.

Instead of encrypting the message itself, a random value is encrypted and then XORed with the respective plaintext block. After that, the counter is incremented (e.g. by 1) and encrypted again. The result is XORed with the next block of the message and so forth. This way, for encryption one has to simply repeat the same steps (encrypt the counter, XOR the result with the ciphertext, increment the counter and repeat).

Here's a link to a diagram of how it works:
https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#CTR

If possible, use existing libraries. It's  easy to get crypto running, but it's hard to get it secure.


Types of Cryptography for a 4-8 bit microcontroller This is more of a research question.

I was wondering what types of crypto algorithms would work best on a small 4-8 bit micro controller.  I recently read a paper called Security Considerations for 802.15.4 Networks and was wondering if anyone out there can think of any other papers or has knowledge about what types of things to consider when implementing cryptography on a low-power, low-memory system.

I read a 2009 ieee paper on implementing RFID on a 4-bit micro controller, but I am looking for papers that will generally apply towards 802.11 or 802.15 standards.  I will propablly be trying to hook a bunch of these controllers together, so I am looking for more of asymmetric encryption.

Public-key encryption on microcontrollers

Erik-oliver Blaß ,  Martina Zitterbart.
"Towards Acceptable Public-Key Encryption in Sensor Networks". 2005.

"dsPIC DSC Asymmetric Key Embedded Encryption Library"
an implementation of RSA, Diffie-Hellman, DSA, SHA-1, MD5.
(Are such 16-bit microcontrollers in your range of interest?)

"Links to Embedded Crypto Implementations"
lists a few implementations of RSA on 8 bit microcontrollers.

"full size" symmetric ciphers on microcontrollers

Many people implement cryptography on a microcontroller very similarly to cryptography on any other CPU -- write a program to do encryption or decryption using the same ciphers we use on any other CPU.
Quite a few modern 8-bit microcontrollers have enough program memory (often called "ROM" for historical reasons, although today it's usually Flash memory) and RAM and processing speed to handle the full Advanced Encryption Standard (AES)(a)(b)(c)(d), Triple Data Encryption Standard (3DES)(a)(b), Enigma(a), RC4(a),
as well as less-known algorithms
such as Alexander Pukall’s PC1 (a).

symmetric ciphers designed for low RAM

Quite a few microcontrollers have 256 bytes of RAM or less. A few full-size ciphers work just fine, but ciphers like RC4 seem impossible to implement in this environment.
A few symmetric ciphers seem specifically designed for this environment -- KeeLoq, TEA, XXTEA, etc.

Other cryptographic techniques for microcontrollers

A few bootloaders for embedded systems use encryption.( "USB PIC Bootloader with XTEA encryption" )

Rather than doing the encryption in the CPU itself, a few systems have an external chip that does crypto stuff.
( CryptoAuthentication, CryptoMemory, Trusted Platform Module, etc. )
Such dedicated circuitry, hard-wired to perform some calculation, often requires significantly less power than a more general-purpose CPU programmed to perform the same calculation.
This way newly-introduced bugs in the software on the main CPU can't possibly leak the secret keys stored in that external chip, or introduce new flaws (new timing attacks, etc.) in the algorithm implemented in that external chip.

8-bit designs typically are VERY cost sensitive and regular encryption/decryption techniques are often not cost sensitive enough...e.g. could double the cost of the product. The question you should ask yourself, is how much encryption is enough for your application. I came up with an algorithm with this in mind. First, consider this random number generator algorithm.

Starts with 2 random variables, x and y, with s (start seed) and this per byte algorithm...

y1 = y + s
x1 = x + y

y starts off as 0 and x starts off as an odd integer. x is the random byte output.

If you have 2 such random number generators and encrypt a byte using:

e = b^r1 + r2

Decryption is done on the other side by using the same random numbe generators and using:

d = (b - r2) ^ r1

The initial s and y values (32 bits total) can be done using a simple diffie helman type algorithm.

Note that this algorithm will get you 255 unique encryption values. After this, y is set to zero again, the x and s values have to be set to new values. This could be done by carefully picking unique starting values at the end of the 255 generation, or you could use another random number generator.

The diffie-helman initialization is slow, but the per byte calculations after that is only 6 operations per byte transmitted/received if you only use the 2 random number generators.....which is very fast for an encryption algorithm and it doesn't require a multiply.

I'd probably give this more thought, but it's got a good idea at it's heart. You could also do the diffie-helman step again once every 5 minutes to increase security.

I call this algorithm the Small Device Embedded Security algorithm or SDES.


How fast does a pseudorandom number generator have to be in order to be competitive? Let $\{x_n\}_{n}$ be the pseudorandom sequence produced by a cryptographically secure pseudorandom number generator $G$. What is the cost of computing a term in the sequence for a competitive pseudorandom number generator (PRNG)?

Let me clarify: among the cryptographically secure PRNG, I would like to know which one has the lowest computational cost.

On modern CPUs, a fast Cryptographically Secure Pseudo-Random Number Generator runs sizably faster than one cycle per byte. We are talking >40Gbit/s. See numbers there. Top contenders are AES-CTR assisted by special instructions, and ARX ciphers like ChaCha.

When using dedicated hardware, the true limit is moving around the generated random bits. We can arbitrarily parallelize CSPRNGs, and we have many efficient designs. For example, Trivium is reported at >120Gbit/s/mm2 using 250nm metal CMOS technology, and state of the art today is about 10nm technology, which is faster and some hundreds time denser.

Update per comment: All modern CSPRNGs require $O(n)$ bit operations to produce $n$ bits, and we want a more precise estimate. ChaCha with $r$ rounds (see source) produces $16$ words each 32-bit with computational cost dominated by $16(r+1)$ 32-bit additions and $16r$ 32-bit XORs. Using NAND gates, a ripple-carry adder is 9 gates, XOR is 4 gates, thus the cost is $13r+9$ NAND bit operations per bit produced. For ChaCha8 (which is hoped to have at least 128-bit security), the cost is $\approx113n$ NAND bit operations to produce $n$ bits (with no consideration for circuit depth).

Update on the security of ChaCha8 per this other comment: I'm reasonably confident that ChaCha8 is at least 128-bit safe, but reluctant to state much more because

ChaCha is an evolution of Salsa20, with the same number of 32-bit additions and XORs, and a faster diffusion. While that could make it safer, I'm using that as safety margin.
In the abstract of the Salsa paper, Daniel J. Bernstein recommends the 20-round version for typical applications, and presents 12 and 8-round variants as reduced-round versions recommended for applications where speed is more important than confidence.
Salsa20 was proposed for eSTREAM, in the category asking for fast software ciphers with 128-bit security. While DJB presents Salsa20/20, Salsa20/12 and Salsa20/8 as 256-bit ciphers (which they are as far as key size goes), I'm not reading him as claiming 256-bit security, especially for the reduced-round versions.
There is a known attack with complexity $\approx2^{249}$ against Salsa20/8, thus definitely it does not have security matching its key size. Again, ChaCha8 differs only by its diffusion pattern.
There is a known attack with complexity $\approx2^{153}$ against Salsa20/7, and as the saying goes: attacks only get better; they never get worse.

It sort of depends on what you are using it for.
You would think that openssl's PRNG, rand, would be
cryptographically secure, and I'm sure it's plenty fast.
But I couldn't help but notice a regular preponderance
of repeated hex digits in every call to openssl rand, using
a value of 16 (for AES 128 purposes).  Given that the average
intel chip comes with AES round calculations in silicon, for
extra speed, it does seem like the search space for brute
forcing AES (without the benefit of the RSA-encrypted key)
has been made smaller by this repetition.

If you know that 3 of your 32 4-bit possibilities will
be repeated FOUR times (or more!) you do save some time
doing a brute force.  If I knew in advance that 31 of
the 32 nybbles would be repeated, I would only have to
check 4096 different keys. (as an extreme example)

I once counted 9 repeated digits on one generation.
I know the goal is for a random distribution, but
when you only have 128 bits, that's not always good enough.

So I imagine even at mind-blowing speeds, there's room for
side-channel surprises.  Good luck!

Here's some results I just generated on the fly:

user0@ii:~$ openssl rand 16 -hex
0fe29badfe8e2300cbe4d1f0eecfdac1
000011223489aabbcccdddEEEEEEffff (6,4x2)

user0@ii:~$ openssl rand 16 -hex
a6f3b7054138c58991b560b6377a567f
001133345555666677778899aabbbcff (4x3)

user0@ii:~$ openssl rand 16 -hex
c2d854a9fdac7e73a9872c12ade2c048
012222344577788899aaaaccccdddeef (4x3)

user0@ii:~$ openssl rand 16 -hex
7e1a3400da787aff51dbddd2fd10067a
00001112345677778aaaabDDDDDDefff (6,4x3)

user0@ii:~$ openssl rand 16 -hex
4785496843d62083ed285572cd1ad6b2
012222334445556667788889abcdddde (4x3)


What are usable entropy sources in a headless machine without /dev/random or any cryptography API? If I have a headless machine (no mouse movements, no keyboard presses, or user input), without any cryptography CSPRNG APIs, where can I collect entropy from?

I believe that on any CPU that you should be able to find at least two sources of noise with physically proven behaviors to create a purely random number.  The first is through oscillator sampling, assuming that you have a fast clock and a slow clock.  The second assumes that you have DRAM, and through the two-way shot noise in the channel, you should be able extract random bit flips in DRAM if you can control the timing.

Clock Sampling

The clock in a system is not a precise as you'd hope.  Generally, you have a core clock that is generated through a PLL, and you also have some sort of realtime clock at 32.768kHz because that will overflow after bit-15 to give you a 1-second pulse.   By sampling the fast clock with the slow clock, you can generate a series of bits; however, there's a few caveats:

oscillator jitter alone is not enough to create randomness
you can actually degenerate the randomness by trying to make it random if you have a poor circuit model.

As an x86 was mentioned (I know the least about this CPU btw), the time stamp counter combined with a 8254 on older machines or HPET on newer machines will get you a fast and a slow clock source.   Michael S. McCorquodale dissertation should have a very good analysis on the clock jitter in both cases, or at least he did at this defense.

DRAM

If you can control the timing of the DRAM, you very likely could get a random noise source due to the fact that the noise in a semiconductor channel is a function two-way shot noise (and not classical Johnson Noise). Let's limit the scope to a single bit.  You would have to put charge on the DRAM capacitor and then gradually delay the timing until that bit gave you a 1 or 0.  The charge amplifier on the DRAM rows would also add to the noise, but I will ignore that component for now.  Carver Mead and Rahul Sarpeshkar both use shot-noise in their neuromorphic engineering papers as a source for entropy on silicon neurons, and circuits people can derive it but I really don't know where an external reference is.  The caveats:

DRAM timing control
assume that you are not near "freeze out" as the shot noise goes away.

I believe that either of these, combined with a hash, could be used as a means to generate a true random number as the noise sources are rooted in physics.  You'll need to grab a cryptographer to take what I described to the next step.

Can entropy be gathered in a system without any hardware dependencies?

No.  Not real entropy.  There's probably some over-used cliche about trying to, but essentially you can't create Kolmogorov randomness without physical processes.

But there's a but.  All computer algorithms execute on hardware, and that hardware is non deterministic at the pico scale.  Hard to predict execution paths, indeterminate gate propagation delays and even electron travel times, amongst others can all produce randomness for harvesting.   The haveged algorithm attempts this.  Even simply reading the system clock repeatedly in a high level garbage collecting language [e.g. Java's System.nanoTime()] is non deterministic.

It's gets even more jittery if you can include a spinning disc drive in the loop somewhere. And don't forget that even virtualised discs are mounted on physical ones.

  Are there any reliable entropy sources?

I suggest not very.  All of the algorithms above have to execute alongside other code, some of which may be unknown, and certainly at unknown locations.  It it difficult to quantify how much randomness your algorithm may have harvested, and that directly undermines the security confidence. And the concept of code portability/cross platform operation is at odds with a harvesting algorithm tied to particular hardware.  So it's difficult to get 128 bits of Kolmogorov randomness in a firm timescale.  You will have to use a large safety factor (say x100) in estimating min.entropy, but it's doable if speed isn't important.  You'll be down to only tens of bits/s on something like an Arduino.

There are even more exotic techniques such as reading DRAM state transitions.   There's a 2018 summary of DRAM based cryptographic primitives here, from TRNG and physical unclonable function (PUF) perspectives.

If your machine has some form of remote/comms access, then you can just fetch entropy over the comms port from a device that has it to spare.


Is it possible to find two sets such that their hash xor summation is the same? Consider two sets $A=\{a_1,a_2,\cdots,a_n\}, B=\{b_1,b_2,\cdots,b_m\}$; $m,n$ can be different. we can calculate the xor summation of each element's hash value: $XOR(A)=(hash(a_1)\oplus hash(a_2) \oplus \cdots \oplus hash(a_n))$ and $XOR(B)=(hash(b_1) \oplus hash(b_2) \oplus \cdots \oplus hash(b_m))$. Is it possible that set $A$ does not equal set $B$, yet $XOR(A)=XOR(B)$?

As for the feasibility of finding such a colliding set, well, as long as the sets are allowed to be relatively long (e.g. at least as long as it bit values being xor'ed), then it is easy.

First off, we assume that the hash output is $n$ bits.  Then, we select $n+1$ distinct values $X_i$ and set $\delta_i = Hash(X_i)$.  Then, we use linear algebra to find a subset of the values $\{ \delta_1, \delta_2, ..., \delta_n \}$ that xor to $\delta_0$ (note, there is a probability that there won't be such a subset; that probability can be minimized by including a few extra values).

With such a subset $\{ \delta_{z_0}, \delta_{z_1}, ..., \delta_{z_k} \}$, we have $$Hash(X_0) = Hash(X_{z_0}) \oplus Hash(X_{z_1}) \oplus ... \oplus Hash(X_{z_k})$$

That is, the sets $\{ X_0 \}$ and $\{X_{z_0}, X_{z_1}, ..., X_{z_k} \}$ collide

In the trivial case, take a compressing hash function $hash$ then there must exist a collision i.e. $ \exists a \neq b $ such that $ hash(a) = hash(b)$. Therefore, $ A = \{a\} $ and $B=\{b\}$ with $A \neq B$ yet $XOR(A) = XOR(B)$. This says nothing about how easy it is to find this collision if the hash function is collision resistant, but it does exist.


Is Convergent Encryption really secure? Recently a company called Bitcasa demonstrated a product of cloud storage. they indicated that they would use "Convergent Encryption" to secure your data and de-duplicate, essentially one copy of the same file between users.

From what I can read on a university paper about Secure Data Duplication which makes mention of "Convergent Encryption" and assuming this is what this is referring too.

My question is, what security implications of using this technology and is it truly secure that you cannot get the key based on chunk data being used to generate different keys between users.

Reference interview on Washington post

If it's implemented properly, it is as secure as any other form of encryption in preventing those who don't know the data from obtaining it from the encrypted data. However, it does have one fundamental limitation that, so far as we know, is inherent in the technology -- Anyone who has the same file you have can potentially prove that you have that file.

The general way such algorithms work is as follows:

The object to be encrypted is validated to ensure it is suitable for this type of encryption. This generally means, at a minimum, the the file is sufficiently long. (There is no point in encrypting, say, 3 bytes this way. Someone could trivially encrypt every 3-byte combination to create a reversing table.)
Some kind of hash of the decrypted data is created. Usually a specialized function just for this purpose is used, not a generic one like SHA-1. (For example, HMAC-SHA1 can be used with a specially-selected HMAC key not used for any other purpose.)
This hash is called the 'key'. The data is encrypted with the key (using any symmetric encryption function such as AES-CBC).
The encrypted data is then hashed (a standard hash function can be used for this purpose). This hash is called the 'locator'.
The client sends the locator to the server to store the data. If the server already has the data, it can increment the reference count if desired. If the server does not, the client uploads it. The client need not send the key to the server. (The server can validate the locator without knowing the key simply by checking the hash of the encrypted data.)
A client who needs access to this data stores the key and the locator. They send the locator to the server so the server can lookup the data for them, then they decrypt it with the key. This function is 100% deterministic, so any clients encrypting the same data will generate the same key, locator, and encrypted data.

There is a weak point that never mentioned: convergent encryption is unable to choose encryption key, if the hash vale is happened a weak encryption key, the encryption is easy to be attacked.


Signing a document: which algorithm to use? What I want to do is to digitally sign a document. I am new to cryptography and was wondering what issues to take into account.
The only criteria is that a textual document signed should produce a code that is different if lines in the same document are shifted. I heard that MD5 is broken and that one should avoid SHA1 (because of NSA etc).

As I said, I am new to crypto. Any suggestions would be welcome!

I guess they would need to go to my website, find the document and check whether the signed code is the same as the document they want to check.

If you assume people are able to trust your website, you could simply list the SHA-256 (for example) hashes of your documents on your website. Perhaps include an URL in the signed document pointing to a particular page on your site that lists the hash for that file.

Trusting others to get the correct hash from your website when they visit the URL would remain unsolved. Someone could intercept the request and return a different hash that matches a modified document they've distributed.

The more complex option is public key signatures.

If you go that way you would use something like GPG/PGP to generate a key-pair, distribute the public key, then sign the documents using the private key. In this case an attacker couldn't produce a different signature that matches your key even if they controlled requests to the documents and your website.

However, you would still need to get your public key into the hands of anyone wanting to verify the signature. An attacker who could distribute their own key as yours could again forge signed documents in your name.

First thing Hashing and digitally signing are different things.

Hashing

  A hash function is any function that can be used to map data of
  arbitrary size to data of fixed size, with slight differences in input
  data producing very big differences in output data.

Digital Signatures

  A digital signature is a mathematical scheme for demonstrating the authenticity of a digital message or document. A valid digital signature gives a recipient reason to believe that the message was created by a known sender, such that the sender cannot deny having sent the message (authentication and non-repudiation) and that the message was not altered in transit (integrity).

To digitally sign a document you can use a public key encryption scheme. This works by having a personal private public key pair. By making the public key available publicly and keeping your private key. You can use your private key to encrypt the message. This message can only be decrypted by your public key! Because only you have access to the private key, others can be sure that you are the sender if your message is decrypted successfully by your public key! RSA is a widely used encryption algorithm in this scheme.
I hope this helps.


Addition step in MD5 implementation In MD5, there are four rounds. After every round, why do we need to add the computed $Q$ values to the initial values and then take this value as input to the next round. For example after the first round, we compute
$$Q^{\text{new}}_1=Q_{60}+Q_{-4}, \ Q^{\text{new}}_2=Q_{61}+Q_{-3}, \  Q^{\text{new}}_3=Q_{62}+Q_{-2}, \  Q^{\text{new}}_4=Q_{63}+Q_{-1}$$
Why cant we directly take the computed values as the input to the next round without adding them to the initial values ?

The reason we, at the end of the compression function, add the input to the compression function, well, that's because otherwise the compression function would be invertible, and that would be bad.

Without that final step, the compression function would be invertible in this sense: given a desired compression function output and a message block, we would be able to find the compression function input.  We would be able to do this because the MD5 compression function is made of 64 steps, and each step is itself easily invertible.  Adding in the compression input at the very end breaks up this invertibility, because the analyst is unable to invert that final step (because he doesn't know the compression function input yet).  He could guess the input at that stage, and then run the rest of the compression function backwards; this turns out to be no more efficient that just guessing the compression function input, and running it forwards.

This invertibility would be bad, because it allows an attacker to do tricks we'd prefer him not to.  For example, we'd want a preimage attack (that is, given a hash value, give me a message that hashes to that) to take (with a 128 bit hash like MD5) roughly $2^{128}$ steps; that is, there is no method that is drastically more efficient that trying random messages and hashing them until you stumble across one with the correct hash.  However, if the compression function is invertible, here is what that attacker can do, given a $Target$ hash value:

Generate $2^{64}$ message prefixes, and generate the partial hashes to that point
Generate $2^{64}$ message suffixes.  When these, he would start with the $Target$ hash value, and compute the hash backwards until he gets the inverse partial hash (having first applied the MD5 final padding).
Given those two lists of 128 bit items, he then looks for a match (and, by the birthday paradox, there's a good chance of being one.

And, if the partial hash of $P_i$ is the same as the inverse partial hash of $S_j$, then he knows that $Hash( P_i || S_j ) = Target$.  This is because, when we evaluate the hash, we first run the compression function on the blocks from $P_i$; at the end of this evaluation, he would come up with the common partial hash value.  Then, he would run the compression function on the blocks from $S_j$ after padding; he knows that, starting at this common value, that results in $Target$.

So, because of this, an attack we had hoped would take $2^{128}$ steps could be done with roughly $2^{64}$ steps.  Making the compression function noninvertible (which the real MD5 does) prevents this line of attack.

This answer is incorrect and resulted from a misinterpretation of the relevant RFC

In the relevant RFC the authors state under "Differences Between MD4 and MD5"

  Each step now adds in the result of the previous step.  This
     promotes a faster "avalanche effect".

So this seems to be their rationale for that step. If it is reasonable, I really can't say.

But irrespective of that, if you want to implement MD5, then yes that step is necessary, as otherwise your implementation would be incompatible with other implementations.


Software implementation of a commutative cipher? I've got an application (detailed below) that calls for the use of a cipher that is commutative.  I've been doing some googling & reading, and there are two algorithms that seem to get mentioned in these discussions--SRA (not RSA) and Pohlig-Hellman exponentiation.  (Supposedly SRA is a variant of RSA?).  I need something strong, so XOR will not serve.

I'd hoped to run across some actual software that implemented one of these guys so I could play around with them & demonstrate a scheme I have in mind, but I have not been able to find any.  It looks to me like these things are not in the source code that comes with Schneier's Applied Cryptography, frx. Can anyone recommend a source for implementations of either SRA or Pohlig-Hellman?

Here's how I'm thinking to use this tech if I can get my hands on it.  I work for a healthcare provider A, which operates in the same geographic area as our colleague/competitor provider B.  We know that we share some patients, but we don't know which, or even how many people we have in common.

We could just swap lists of say, the SSNs of our patients & find out who we share, except that we don't really trust each other to treat this sensitive data w/the care that it's due, and wow would people freak out and hate us if it got out that we were making free w/their SSNs, etc. etc..  So--please take for granted that sending raw SSNs is neither practical nor desirable.

But here's what we maybe can do.  I grab my commutative-cipher software, generate an encryption key, save it off somewhere safe, and produce a file of encrypted SSNs (each SSN encrypted separately with my key).  My colleague at provider B does likewise.  Then we swap encrypted lists, and each encrypt the other guy's encrypted SSNs with our own keys.  Then we swap the doubly-encrypted lists.  Because the cipher is commutative, encrypting with key A first, and then key B should give the same results as encrypting with key B first and then key A.  Which means that any values that are shared on the two doubly-encrypted lists represent the same SSN, and therefore a shared patient.  So we know exactly who we share, without exposing the SSNs of our entire patient list.

To clarify a little, you need "encryption" that is commutative, deterministic (otherwise the commutative ciphertexts won't necessarily match even if the plaintexts do), and has a private encryption function (otherwise given that it is deterministic and the plaintext space is small, an exhaustive search would be possible). For example, Elgamal is commutative but it is also randomized and public key. Encryption is in quotes because, since you never decrypt, you actually just need a trapdoor function with those properties.

Pohlig-Hellman and SRA are suitable.

As far as implementations go, I do not know of any. However Pohlig-Hellman would be easy to implement with just a number theory library (it is just a single modular exponentiation -- you don't need to decrypt in your application). If you have a DSA library that has a function to generate a public key from a secret key, you can use that as the encryption function.

Similarly, SRA is just RSA with two key pairs. If you could call the key generate function of an RSA implementation is such a way as to get $e,d$ if you supply $p,q$, then that would work.

Both of these ciphers are old and were developed before certain attacks were known. For Pohlig-Hellman, you should work in a multiplicative subgroup and this requires encoding the plaintext. SRA could leak the Jacobi symbol of the plaintext like RSA (I think even if $e$ is not known?).

Finally, the application you are implementing is called "private set intersection." There are lots and lots of papers on how to do it, and potentially some implementations of the whole protocol. There are some issues with the way you are implementing it assuming that one of the parties is malicious.

If both parties are honest (only submit true values) and fair (one party learns the result before the other), it seems ok. But there are all sorts of attacks otherwise that could be resolved by using a private set intersection protocol designed for exactly this purpose.

I suppose there are some commutative asymmetric ciphers out there.

$\newcommand\Enc{\operatorname{Enc}}\newcommand\KStr{\operatorname{KStr}}$But if you have longer messages, I would consider using a synchronous (binary) stream cipher. This is an algorithm which just outputs a long stream of pseudorandom bits, which then can be XOR-ed with the plaintext or ciphertext to get the other one: $\Enc_k(P) = \KStr(k) \oplus P$.

Use a stream cipher with random/unique initialization vector (a new one for each record) to make the keys reusable.

For two keys $A$ and $B$ and a plaintext $P$, we have then

$$ \Enc_A(\Enc_B(P)) = \KStr(A) \oplus \KStr(B) \oplus P = \KStr(B) \oplus \KStr(A) \oplus P =  \Enc_B(\Enc_A(P)),$$

i.e. just your commutativity.

After actually reading your use case description, it looks like it won't work easily for your use case: you would need to manage the initialization vectors in a way that the same SSN is always encrypted with the same IV, without giving away something about the SSN by the IV. Sorry.


Given infinite unencrypted and encrypted texts, can I find the algorithm? Given an infinite amount of both unencrypted and the corresponding encrypted text, would I be able to calculate the algorithm? I am relative new to cryptography and don't know if I would be able to find how the unencrypted text is encrypted... Is this possible? If so, what should I study?

summmary

In general, no.
An attacker who has lots of ciphertext+plaintext pairs may never be able to reverse-engineer an algorithm from them.
An attack may not even be able to distinguish which one of a large group of known encryption algorithms was used to generate those ciphertexts.

However, various weaknesses in some algorithms and protocols are known.
If such an algorithm was used, the attacker may find it relatively easy to rule out all but a few or perhaps only 1 of the known encryption algorithms.

details

Some people who build modern ciphers try to make their ciphers "indistinguishable from random".
Several modern ciphers (especially ones intended for use in steganography) are not currently known to be susceptible to such a distinguishing attack.

No matter how many ciphertext+plaintext pairs the attacker collects that were properly encrypted using a single one of those algorithms using a single long-term key,
there is no known practical way for that attacker to distinguish a new message encrypted using the same algorithm using the same long-term key from a freshly generated series of bits from a hardware random-number generator.
This implies that there is no known practical way for that attacker to discover which one of those algorithms was actually used.

Cryptanalysts have discovered distinguishing attacks for many vulnerable ciphers.
If an attacker collects enough ciphertext-plaintext pairs encrypted by such a vulnerable cipher, that attacker can rule out most other ciphers, narrowing down the possible algorithm to a few or perhaps only 1 known vulnerable encryption algorithm.

When an attacker has samples of both the plaintext (called a crib), and its encrypted version (ciphertext), the attacker can mount a known-plaintext attack.

The people who build modern ciphers try hard to make their ciphers immune to known-plaintext attacks.
Most modern ciphers are not currently known to be susceptible to known-plaintext attacks.

However, many historic ciphers (most famously, the Enigma cipher) can be partially or completely broken by a known-plaintext attack.

Many distinguishing attacks and known-plaintext attacks depend on the person doing the encryption using the same key for large numbers of messages.
Sometimes that number is so extremely large that these attacks are impractical.
Other times that number is large but not improactical, and cryptographers recommend periodically rekeying long before such attacks are practical (RFC4253, RFC4344, etc.).

In practice, many communication protocols transmit the specific encryption protocol used, transmitted in plaintext in the header before any ciphertext, at the beginning of every message.
An attacker only needs to look at that header to know which encryption algorithm was used.

If someone encrypts enough messages with the same key using a block cipher in electronic codebook mode,
and an attacker gets enough ciphertext-plaintext pairs,
then even without knowing which particular block cipher is used,
the attacker can decrypt any block in any new encrypted message whenever a block of plaintext in the new message happens to match a block of known plaintext.

In theory, if an attacker has an "infinite amount" of computing power,
that attacker try every possible encryption key in every known encryption algorithm and see if it "works".
Such a brute-force attack can in theory recover the key for almost all known encryption algorithms.
(The one-time pad and closely related ciphers are completely immune to a brute-force attack).
Fortunately for people who are not attackers, the amount of work required for such a brute-force attack usually makes them impractical.

Did you know the algorithm ? This is the central question.
In modern cryptography, the algorithm is public while the all secret lies in the key. Knowing the algorithm allows analyst to quantify the strength, or the intractability of the mathematical transformation.

You alse have to make a distinction. Two main classes exist between Stream Cipher and Bloc cipher.

In Stream cipher, the key is as long as long as the message, and the question is not well asked. For example OTP case don't recommands to use the same key twice.

In bloc cipher by definition input-output sizes are bounded. for a m-bit cipher size, there are $(2^n)^{2^n}$ binary applications from input space to output space. Then we coudn't have an infinite number of (plain, cipher) pairs.


How can I use SSL/TLS with Perfect Forward Secrecy? I'm new to the field of cryptography, but I want to make the web a better web by setting up the sites that I host with Perfect Forward Secrecy.  I have a list of questions regarding the setup of Perfect Forward Secrecy.  Here it goes:

Can my choice of certificate authority hinder the use of Perfect Forward Secrecy?
How can I create the strongest certificate using ONLY Perfect Forward Secrecy (meaning if the browser can't use PFS, it won't load anything)?
Are there any extra settings that I need to know about for configuring my sites to use these certificates (especially since I only want PFS)?
Anything else that I should know, feel free to tell me.  I'm completely new to this idea.

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using.

This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, certificates have not entered the picture at all. This is because whether or not a connection has perfect forward secrecy is determined by how the session key is derived. And how the session key is derived is determined by the ciphersuite in use. So, the ciphersuites that use ephemeral Diffie-Hellman (DHE) or the elliptic-curve variant (ECDHE) will have perfect forward secrecy while the other options will not.

Thus, in order to configure PFS for your site, what you want to configure is your web server's ciphersuite-selecting options. More on this below.

  Can my choice of certificate authority hinder the use of Perfect
  Forward Secrecy?

No. Perfect forward secrecy protects against the revelation of master keys. CAs do not have access to private (master) keys; a certificate from a CA is a signed public key. The CA is there to say "okay, client, I have verified that the public key here is indeed associated with <host>, it's safe." (Or, rather, the fact that it's signed by the CA says this.) Thus, your choice of CA will not impact PFS in any way.

  How can I create the strongest certificate using ONLY Perfect Forward
  Secrecy (meaning if the browser can't use PFS, it won't load
  anything)?

As you can see, certificates are unconnected with the choice of ciphersuite (and hence PFS).

Instead, the web server you use probably has a ciphersuite configuration in its SSL configuration. There are usually two relevant options: first, the ciphersuites that you want your server to use, and second, how the server picks the ciphersuite. Here is the relevant section in my nginx configuration:

ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_ciphers ECDHE-RSA-AES128-GCM-SHA256:ECDHE-RSA-RC4-SHA:ECDHE-RSA-AES128-SHA:RC4:HIGH:!MD5:!aNULL:!EDH;
ssl_prefer_server_ciphers on;

The first line tells nginx to use those four protocols, as is apparent. The third line tells nginx to prefer its own ciphersuites over the client's. The point here is that we want to control exactly which ciphersuite will be selected. A client may send an ordering that suggests a non-PFS ciphersuite; hence, we trust the server.

The second line is where the magic happens. Note that I manually specify that I want those three ECDHE-* schemes first if they are supported by the client. From there, I fall back to the usual schemes. I feel the need to emphasize that I don't disallow clients that don't support PFS; some encryption is better than no encryption at all. Not all clients do support PFS, so this is pretty important. I realize your question said you want only PFS ciphersuites, but I would advise against that. With the above nginx configuration, the vast majority of connections' selected ciphersuites will have PFS. The configuration for Apache is apparently quite similar, which is not surprising given that both use OpenSSL.

To that end, a useful tool: the SSL Labs SSL Test. It gives you a basic grade on your SSL configuration. See, for example, Google's grade (click on one). It has a little green box under the grade informing you that the site supports PFS for all its tested browsers, and if you scroll down to 'Configuration', you will see a ciphersuite priority list, including which ciphersuites have PFS, as well as "simulated handshake" for the common browsers of the day.

Warning: it is widely believed that the ECC curves used for PFS have got NSA back doors in them.  If you're up-to-no-good, setting up to use curves and algorithms that were designed and promoted by the NSA themselves might not be the best solution.


Can one use a reversible hash algorithm as a compression function? As we know any text, file, byte...in SHA-256 output will be returned as 64 hex length. Is it possible to create cryptography that can do the same thing as SHA-256 but can be reversed, so if we have the output of 64 length of hex number, we can reverse it and get started input like "i love programming"? This will be soo cool way to compress huge text. Is it possible?

Strictly speaking, all hash functions are compressing since the output can be smaller than the input, but I imagine you're asking about compressing data that can later be losslessly decompressed.
This is impossible due to the pigeonhole principle. The fact that the fixed output space of a hash algorithm is smaller than the input space means that there will always be multiple possible inputs for the same output. Even if you could find a preimage (i.e. "reverse" the hash), you would not know if it is the original preimage or just a preimage. If the input size was sufficiently small (smaller than the hash) then it may be possible since you can discard larger preimages and only keep the very finite number of small ones that make sense (e.g. only valid ASCII strings), but then it's not compression.
As an extreme example, imagine a "hash function" with a trivial preimage attack: a 1-bit CRC with the polynomial x + 1 (i.e. an even parity bit). If I give you the output of this function and the output is 1, you will have absolutely no idea what the input was. You can compute an input, but you can't find the input. For a 1-bit hash, half of all possible inputs in the input space map to that same output!

This impossibility is the basis of the popular joke from Schneier Facts:

For Bruce Schneier, SHA-1 is merely a compression algorithm.

Yes, it is possible provided you allow for hashes that are not necessarily a fixed length. This is essentially what content based addressing is. The content can be "any text, file, or byte" and it is addressed by a hash of it. For an example of this you can check out IPFS. You can share a short address of a file with someone else and they can decompress that hash back into the original piece of content. This works by maintaining a mapping between these addresses and the content.
While forest says that this is impossible due to the pigeonhole principle when using a fixed size hash output, IPFS gets around this by being able to support an arbitrary number of hash functions which can each have an arbitrary length. By varying the hash function or length you will always be able to find an address that is not currently used.


What are the consequences if someone finds the accessible 1600-bit block $X$ and $R$-bit block $V$ such that $\text{Keccak-}f[1600](X \oplus V) = X$? Let $H$ denote any hash function based on the sponge construction. Let $F$ denote its underlying function that transforms the $L$-bit state (for SHA-3, $F = \text{Keccak-}f[1600]$ ). Let $R$ denote the bitrate.

Note that the padded message $M$ has the following form:

$$\text{pad}(M) = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots \mathbin\Vert B_{N-1} \mathbin\Vert B_N,$$

where $B_i$ denote $R$-bit blocks.

Consider the possibility that there exists some $L$-bit block $X$ and $R$-bit block $V$ such that $F(X \oplus V) = X$ (obviously, assuming that the xoring takes place in the same position where the padded message blocks are xored into the state). Moreover, there exists some sequence of $R$-bit blocks $$S = B_1 \mathbin\Vert B_2 \mathbin\Vert \ldots B_{Y-1} \mathbin\Vert B_Y$$ that lead to the state $X$. Doesn’t this mean that if someone knows $S$ and $V$, it would be very easy to choose any suitable sequence of $nR$ bits (where $n$ is any natural number greater than 0), denote it by $T$ and generate arbitrarily many different messages such that
$$\begin{array}{l}
{\text{pad}(M_1)} = S\mathbin\Vert T,\\
{\text{pad}(M_2)} = S \mathbin\Vert V \mathbin\Vert T,\\
{\text{pad}(M_3)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\
{\text{pad}(M_4)} = S \mathbin\Vert V \mathbin\Vert V \mathbin\Vert V \mathbin\Vert T,\\
\ldots?
\end{array}$$

But this means that $H(\text{pad}(M_i))$ is always the same for any $i$. What are practical consequences for $H$ if someone manages to find such a combination of $S$ and $V$, and then publishes it immediately (so that this combination is in open access for everyone)? That is, what practical applications (use cases) of $H$ will be impacted?

Then you've found a collision in SHA-3, and you get a prize.

There is a choice of prizes:

You could get your name on a virtual piece of paper that makes a lot of people excited and causes exceptionally insufferably tedious debates on Hacker News.
You could get a large number of unmarked bills in small denominations and possibly an unwanted piece of lead in your head by selling the collision on the black market.
You could get the fruit of exploiting the collision in real-world applications, with a lot more effort, and who has time for that kind of effort anyway?


Twofish vs. Serpent vs. AES (or a combo) I've seen some posts and info online, but they are from 2009, 2010, 2011 or 2012, which is 3-6 years ago, which is a very long time. So I'm looking for an up-to-date answer about which of these is the safest encryption to be used, or rather most unbreakable? Particularly interested in encryption programs, so performance would also interest me, not only security.

I think things have changed since Snowden's postings, though then again - I know that a file encrypted with some sort of TrueCrypt algorithms remains uncracked after a few years of trying in the FBI.

So, having that in mind, I'd like to know more about it all so that I would be able to choose the right algorithm for me.

None of Twofish, Serpent and AES are currently known as broken, so as far as security is concerned, you can use any of them. AES has a slight advantage because it's very widely used, so if it gets broken you're more likely to hear about it and get relevant software updates quickly.
The Snowden postings haven't changed much as far as cryptography usage is concerned. They confirmed what was generally suspected before, which is that the generally-accepted cryptographic primitives are safe even from NSA-level adversaries¹; it's the systems and sometimes the protocols that are insecure. What's important is not your choice of primitive (as long as it's one of the generally-accepted ones, e.g. one approved by a NIST standard), but your choice of software.
AES has the advantage that high-end x86 and ARM CPUs include hardware acceleration for it.
If you're a user of cryptography, as opposed to an implementer of software like GPG, keep in mind that if you're typing the letters A-E-S into your code, you're doing it wrong.
¹  You might consider Dual_EC_DRBG to be an exception, but few people used it because it had no obvious security benefit, and its potential to be backdoored was known, and it was slow.

Twofish's composition is actually more secure than AES and is rendered unbreakable from a theoretical perspective and physical on the other hand Rijindael (Known as AES) is breakable in some theoretical scenarios. Due to Rijindael's higher efficiency, it was selected as the AES or Advanced Encryption Standard because both standards were regarded as so secure it was just faster to addopt Rijindael as AES due to it's high efficiency. But if you really want the best encryption use Twofish, it is impossible to break (except for bruteforce of course) and the only feasible way any mortal could break a Twofish password with at least 128 Bits and an 8-6 character password is if they rented a data center and waited a couple years until they finaly broke your password using bruteforce.


Reordering non-block-aligned parts with DES in ECB mode I was given a ciphertext file which was encrypted using DES in ECB mode. It is known that the plainttext that was encrypted has the following form:

Each line of text consists of a payroll followed by a name (no spaces):

32 characters for the name;
8 characters for the pay amount;
1 newline.

An example plaintext file would be:

abcdefghikabcdefghikabcdefghikab00000000
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab10010010
abcdefghikabcdefghikabcdefghikab11111111

and it was encrypted using this command (of course the key was not given, for obvious reasons):

openssl enc -e -des-ecb -nosalt -in plaintext.txt -out ciphertext.enc

The ciphertext file is of size 288 bytes since there are 6 newline ('\n') characters and DES encrypts in 64 bit blocks it's easy to tell that there are 7 entries in this payroll list.

The Objective: exchange the first line with the last.

If all the entries were on one line with no spaces this would be an easy task as DES in ECB mode you can move around the 64 bit blocks without being detected. All I would do is take the first 40 bytes and exchange them with the last 40 bytes. However since there is a '\n' character at the end of every line this approach does not work. I feel a bit stuck. All I'm looking for is a point in the right direction.

If the plaintext format is indeed as you describe, then you're out of luck: the insertion of the newlines and the consequent shifting of the plaintext records is enough to disrupt any structure in the ciphertext.  If the plaintext were longer, say, 8 records, then it could work, but with just 7 records there's no way to switch the first and last record simply by shuffling ciphertext blocks.

However, I suspect you're mistaken about the presence of newlines in the plaintext.  Specifically, since the encryption command you were given does not include the -nopad option, the openssl enc command applies PKCS #5/7 padding to the plaintext before encrypting it.  In order to be unambiguously reversible, this padding scheme always increases the length of the plaintext by at least one byte — in particular, it causes any plaintext length between 280 and 287 bytes inclusive to produce a ciphertext of 288 bytes.

Thus, I suspect that your data actually has no newlines, and simply consists of seven 40-byte fixed length records, plus 8 bytes of padding.  Keeping the last 8 bytes of the ciphertext in place, and switching the first and last 40-byte chunk of the ciphertext preceding it, should do the trick.

Well, DES is weak and since you can guess a plaintext you can use a rainbow table to crack the key and then of course decrypt and re-encrypt the message.

Apart from that I don't think you can re-order the blocks to change the first and last line, if you really want to do this specific operation.


Is this the right way to implement ElGamal scheme over Elliptic Curves over prime field? I'm fairly new to Cryptography, especially elliptic curves in general. I learned to do Point Multiplication, Scalar Multiplication and also programmatically implemented them. But I was trying to do ElGamal scheme because I felt intrigued by the subtlety of it.
The problem that haunts me is this:
Suppose, I have a generator point G on an Elliptic Curve (say SECP256k1 or any curve) , an integer x, which is the private key of this scheme, and I generate the public key P= [x]G . Then, I encode the message to a single number (e) that will be surely less than p, the prime number of the field (256 bit).

ENCRYPTION : I generate a random number k, less than N, where N, is the order of the curve, and also: R = [k]P .
I also choose a point C = [k]G. Then I take the x coordinate of R, and do: (x_coordinate of R*e) modulo p -> this will be the cipher text.

DECRYPTION: I take the chosen point C, multiply it with x (private key) to recover the point R back, then I do :  (cipher_text*((x_coordinate of R)^(-1) modulo p))modulo p to recover e , the encoded message, which is then decoded back to plain text !

MY CONCERNS:
[1] Was that the right way to encode the message?
[2] If x_coordinate of R * e was smaller than 256 bits then modulo would output the same x_coordinate of R*e which can be easily factored on a computer, and x_coordinate of R could be recovered !

EDITS:
What can be the maximum size of x_coordinate of R * e when taking modulo p ? I understand that it should be less than p, but even when I take blocks of plain text such that Rx*e alone exceeds ( 485 bits)the bit size of p (256 bits) I'm able to recover the encoded message back ! I do not know the reason for this creepy behaviour!!! ? Sorry, I'm fairly new to the math of all this !!! BUT: If x_coordinate of R*e is of the order of 2000 bits I totally loose data !!! Infact I am getting it wrong if thats the case!
This is what gives me trouble:

/************************
     Code for illustration of
     my mathematical problem
******************/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <gmpxx.h>

using namespace std;
mpz_class ModInverse(mpz_class a, mpz_class b)
{
    mpz_t inv;
    mpz_init(inv);
    mpz_invert(inv, a.get_mpz_t(), b.get_mpz_t());
    return mpz_class(inv);
}
int main()
{
      // Prime used by SECP256k1
      mpz_class p=mpz_class("115792089237316195423570985008687907853269984665640564039457584007908834671663");
      //Let this be some encoded message ...
      mpz_class msg=mpz_class("123115792089237316344566776544467896775567567584007908834671663758400790883");
      // Let this be the x coordinate of R
      mpz_class x=mpz_class("712164785702978780789493774073370493892893827485075314964804772812648384");

      cout<< "Encode Message :  "<< msg <<  endl;
      cout << "\nx coordinate of R * msg"<< msg*x << endl;
      cout << "Product bit length: " << mpz_class(msg*x).get_str(2).length()<< endl;
      // Bit length exceeds modulo bit length
      mpz_class cph=(msg*x)%p;
      cout << "Cipher : "<< cph<< endl;

      cout << "\nDecrypted message : "<<  (cph*ModInverse(x, p))%p<< endl;
      if ((cph*ModInverse(x, p))%p == msg){
      cout << "    Crypto successfull !!!"<< endl;
      }
}

EDIT 2:
If (x coordinate of R * e ) is less than p then with sufficient amount of cipher text of that form, can an attacker with some cryptanalysis crack it ??? I'm reading a message in blocks...

Sorry If I'm wrong !!!

Every help will be appreciated!!!

It does not matter what encoding scheme you use for the message, as long as it is reversible: you should be able to recover the message from e.
Assume you do not know $e$ or $R_x$ (the x-coordinate of $R$). You are given $$e \cdot R_x \mod p$$
For any possible message $e'$ that you could guess, there is some integer $n$ such that $$e'\cdot n \equiv  e \cdot R_x \mod p$$
(exercise: what is this $n$?)

If you could determine which of $e$ and $e'$ was the correct message, then you would be able to tell which of $n$ and $R_x$ is the correct x-value of the shared secret $R$. But we assume that the attacker is not able to distinguish $R$ from a random point on the curve (this is the Decisional Diffe Hellman assumption).

Essentially, you do not need to worry about an adversary "factoring" $R_x \cdot e$, because in the integers mod $p$ there is not a unique way of factoring a number, for exactly the same reason that there is no unique way of factoring into rational numbers: $6 = 3\cdot 2$, but it also equals $4 \cdot \frac{2}{3}$ or $95 \cdot \frac{6}{95}$


How to construct a variable length IND-CPA cipher from a fixed length one? Suppose we can construct a secure (IND-CPA) encryption scheme for fixed length messages. I was wondering if there is a natural way to extend this construction for messages of variable length such that it is still an IND-CPA secure scheme.

The typical way to make an encryption scheme work for variable length message is to use a mode of operation.

Since you are starting with an already IND-CPA secure cipher, even the often despised ECB mode will work. That said, you will still need padding to make the plaintext length a multiple of the blocksize. If adding padding is out of the question, a streaming mode such as CTR will work.

If you want a real variable length, you loose the IND-CPA security:

You have to make all possible ciphertexts equally long, so that the attacker can not distinguish between the longest possible message and a 1 bit message. If maximum length is not known at the key generation, your ciphertexts would need unlimited length.

If you allow the attacker to know the message length (this isn't IND-CPA anymore), you can choose any kind of encoding (e.g. blockwise or arithmetically) and apply encryption on each part individually.


Finding the prime factors of $n'$ given the previous $n$ and its prime factors $p$ and $q$ Say I have a very large number $n$ = $pq$ where $p$ and $q$ are prime.

A new number $n'$ is generated by increasing these prime factors. How can I find this new number's prime factors?

On one hand, what's asked in the question's title is finding the factorization of $n'$ given the factorization of "the previous" $n$ as $n=p\,q$. As far as we know, that can't be done for $n'$ of cryptographic interest, for a definition of "previous" implying a small increase in value.
That's part of surrogate factoring, which is to factorization what perpetual motion is to movement.

On a second hand, what's asked in the question is different: finding the factorization of $n'$ given that it is of the form $p'\,q'$ with $p'$ (resp. $q'$) a prime "generated by increasing" some known $p$ (resp. $q$). That makes the task easy, for a definition of "increasing" implying a small increase in value. All there is to do is explores the integers $p'$ above $p$ sequentially, and try if they divide $n'$, until hitting the factorization; it is not even necessary to check that $p'$ is prime.

On a third hand, a comment tells that "$n$ grows by a digit each round", which implies that at least one of $p$ or $q$ has changed a lot in value. If only one has changed a lot, we can try the above method on both $p$ and $q$. If both have changed, and we have no clue about how, then the factorization of $n$ is useless to find that of $n'$, and we are back to the problem of factorization of $n'$ without clue, which can be handled up to 800 bits (240 decimal digits) give or take 50%, depending on resources.

if p is the smaller factor
$n = p * q$
$q = \frac{n-p}{p}+1$

By iteration starting from p = 2, p + 1 if the equation is false
$n = p * q$


Is it overkill to run a key generated by OpenSSL through pbkdf2? I'm generating a key & iv with OpenSSL via:

key = OpenSSL::Cipher::Cipher.new('aes-256-cbc').random_key
iv = OpenSSL::Cipher::Cipher.new('aes-256-cbc').random_iv

Then I am running the random key through:

salt = OpenSSL::Random.random_bytes(32)
OpenSSL::PKCS5.pbkdf2_hmac_sha1(key, salt, 2000, cipher.key_len)

My question being, is this overkill or make the random key generated by OpenSSL weaker? Would it be sufficiently secure to just use the key without running it through a pbkdf2 function?

Any advice would be greatly appreciated.

Thanks!

PBKDF2 is designed for low-entropy passwords. Assuming your key is generated by a CSPRNG, then running it through PBKDF2 is redundant.  I don't, however, believe it could be weaker than the original key.

Considering we have seen unintentional (and intentional?) bugs in crypto recently, I think it would be prudent to chain together different algorithms and sources of entropy, if possible.