# Tag Info

## Hot answers tagged algorithm-design

23

Most encryption is based heavily on number theory, most of it being abstract algebra. Calculus and trigonometry isn't heavily used. Additionally, other subjects should be understood well; specifically probability (including basic combinatorics), information theory, and asymptotic analysis of algorithms. There's also more math that's worth knowing to be a ...

18

Yes, this is a widely-used cryptographic construction called a stream cipher. For more information about this and other encryption schemes, Coursera's cryptography class is a good resource.

17

People found MARS to be clunky and overly complex, leading to more effort for implementation and optimization, and also a less clear overall security picture. Assessments of "security" are, in fact, extremely subjective, because they rely on speculations about unknown future cryptanalytic attack, empiric traditions (e.g. "more rounds" = "more security"), ...

16

It's a good question. As pg1989 said, this is the basis behind stream ciphers, which are very fast in practice. I thought I'd quickly expand upon your statement that "the one-time pad is the perfect cipher and impossible to crack." This is true, in a sense, but it's worth pointing out that sometimes an attacker wants to do something simpler than "cracking" ...

11

First, and I know this isn't exactly the answer you're seeking, but I'd mull over it for a while. Hopefully you have read Schneier's Memo to the Amateur Cipher Designer; it speaks the truth. In short, before you try to go the route of publishing your algorithm, here are some things you should consider: What makes your scheme compelling to study? Is it ...

6

Your question first calls for a remark, the XOR itself already is an instance of taking a modulo. Namely, XOR is just another name for addition modulo 2. As a consequence, using modulo n can be seen as a generalization of the XOR to larger sets. A simple example is Caesar's cipher which adds a key modulo 26 (the size of the alphabet). To come back to the ...

6

@dr jimbob gives a pretty solid answer, so let me just summarize it: finite fields. Regardless of the area of cryptography you are interested in, you always end up with finite fields, in particular Zp (with p prime), for RSA / DH / DSA / some elliptic curves, and Z2 and extensions thereof (GF(2m)) for symmetric cryptography and some other types of elliptic ...

5

The Skein family of hash functions (submitted to NIST for the SHA-3 competition, but not selected as the winner) has a really well-written paper that tries to go into detail for how it was designed, how constants were chosen, etc. It might be a good place to start.

5

Points 3 and 4 are a secure way of storing the input to bcrypt (with appropriate choice of parameters for bcrypt). Points 1 and 2 aren't necessary but don't harm: they would add a small amount of extra computation for an attacker is possession of the password database that wants to do a dictionary attack; the attacker wouldn't be able to straight-out use ...

5

If using a cryptographically-secure random number generator then the result is a stream cipher. If using actual random numbers, then it's a one-time pad. Any output you get from a random source needs to be run through a randomness extractor anyway in a 2:1 ratio (2 bits in, 1 bit out). Don't forget to provide a MAC along with the ciphertext to prevent an ...

5

Congratulations you just reinvented the stream cipher. The main strength of the one-time pad is that the key space is as large as the message space. This means that any cipher-text only attacks always fail because all plaintexts are valid. This automatically means that any construct that decreases the key space (like using a seed for a PRNG) severely ...

5

A block cipher is (or tries to be) a pseudorandom permutation on a given space. Let $\mathcal{M}$ be the set of $n$-bit blocks for a given $n$. There are $2^n$ possible block values, and a permutation on $\mathcal{M}$ sends each block value to another value. There are $2^n!$ such permutations. A block cipher is a mapping from key values (in a given key space ...

5

You should read the Wikipedia article on finite fields. For each prime $p$ and for each $n >0$, there is a unique field of order $p^n$ (up to isomorphism). This field is usually denoted $F_{p^n}$. Now, for $n = 1$, the field $F_p$ can be identified with the set $\mathbf{Z}/p\mathbf{Z}$ of integers modulo $p$, which is also sometimes denoted ...

5

At the time of answering, the question was can insecure algorithms be combined to form a secure algorithm? Yes: Think of any secure round-based block cipher. The independent rounds are not secure, but put together the overall cipher is. I think my favourite example is (currently) the Even Mansour cipher, which combines two xor operations and one unkeyed ...

5

The probability of someone 'getting lucky' with a guess at a key for a decent cryptosystem is crazily low, but yes: it is possible. However, there are methods that can 'survive' even this. For example, consider the one time pad. In this system the key and plaintext are xor'd together to form the ciphertext, and to decrypt you xor the ciphertext and key. ...

4

This is at least as secure as the original cipher. The only case I can think of where it would be less secure is if the security of the cipher relied on some special relation between the round keys, but I don't know of any ciphers that have this requirement. Most ciphers derive their round keys from the encryption key in a linear way. One example of a ...

4

From what I understand from your question, you are describing a stream cipher. If the one-time pad is the perfect cipher and impossible to crack, why would the following algorithm not be one of the strongest ... You're on the right track; a one-time pad is essentially a perfect (unbreakable) stream cipher. Without going into (any) mathematical ...

4

The lowest level of mathematics required would be binary mathematics like the XOR operator. If you can understand that then you can understand a one-time pad which is mathematically unbreakable. Most other fields of cryptography focus on making life more convenient for the user e.g. using a single key for all communications at the expense of ...

4

For any value $x$ chosen randomly in a set of size $N$, and hash function $h$, publishing $h(x)$ allows for an exhaustive search on $x$ with average cost $N/2$. This is unavoidable. The problem with passwords is that, by virtue of fitting in the brain of a human, they tend to come for a set of potential passwords of relatively small size $N$. We try to cope ...

4

eBACS, as given by CodesInChaos, is a great resource, and it provides much more data than I could hope to give in this answer. However, the page is not explicit about whether or not AES-NI was used — looking at the results, it doesn't seem so. For an extremely shallow analysis, but allowing us to know for-sure about hardware acceleration, we can use ...

4

If your key material is properly random and at least as long as that which is to be encrypted, and indeed each key is used only once, then one-time pad is indeed applicable. As was noted: Distribution of keys will be a hard problem. OTP makes practical sense only in scenarios where keys can be distributed at some time T, then used for encrypting and ...

4

The entire block consists of a $n$ bit nonce and a $128-n$ bit counter. Typically $n=64$. The nonce needs to be large enough so that every message under the key can have a unique one, and the counter needs to be large enough that every message block can have a unique counter value. Typically, the counter is initialized to 0 and then incremented by 1 for ...

4

Well, for one thing, you are not using a "One Time Pad". A "One Time Pad" means, by definition, that someone generates a pad of numbers using true randomness (and not algorithmicly), and that no potential adversary has any information on what that pad may contain. Then, that pad is given to both the sender and the receiver, and then the sender uses it to ...

4

I understand the question as you have a single 4-bit S-box, which you first apply rowwise, and then columnwise. As already mentioned, this is equivalent to a large S-box $\mathcal{S}$ $$c = \mathcal{S}(m\oplus k_1)\oplus k_2.$$ This is a well-known Even-Mansour cipher, and it can be broken with complexity $2^{n/2}$, which is $2^8$ for your $n=16$. The ...

3

This question can be answered in several way depending on the exact meaning you intend for more secure. First answer: No, it is not more secure in general. The most you can expect is "at least as secure" not "more secure". A typical example of this behavior is Even-Mansour encryption where using twice the same key is as secure as using two independent ...

3

Since I have not received any reply from Mr. Rivest's office after bugging them with a total of four emails in four weeks, I have no other option than to give up on hoping I ever receive a replyfrom his office. After spending 6 weeks hunting down information all over the internet (and not receiving any reply to my emails), I am currently suspecting that MD1 ...

3

Summary. The short answer is: Cryptography would be insecure. Any encryption you can do with a non-deterministic algorithm, can be broken (in approximately the same running time) by another non-deterministic algorithm. Non-determinism is extremely powerful. If you give everyone access to non-determinism, then secure encryption becomes impossible: the ...

3

It depends. There is no single answer, and no single recipe that works for all block ciphers. The permutation is chosen to work well with the rest of the block cipher design. Therefore, this question can't be answered in general. A question like "Why did cipher X use Y as its permutation?" would be more meaningful and more answerable. For instance, ...

3

John Kelsey, Bruce Schneier and David Wagner proposed paper "Key-Schedule Cryptanalysis of IDEA, G-DES, GOST, SAFER, and Triple-DES" and they presented new attacks on key schedules of the block ciphers. About "A 768-bit DES variant uses independent round subkeys" they said: A 768-bit DES variant uses independent round subkeys [Ber83]. This variant ...

3

The design documents for Rijndael explain exactly how the designers proved its resistance to differential cryptanalysis. Read their submission to the AES competition process, particularly Section 8.2 and the Annex. To understand their approach, it will probably help to understand differential cryptanalysis and read some of the related literature. You can ...

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