Programming Praxis

I don’t know if today’s exercise comes from an interview question or from somebody’s homework, but it’s a good exercise:

Given two strings, determine if they are the same except for exactly one difference. Two identical strings fail to match. Two strings that differ in two or more characters fail to match. Two strings with lengths that differ by one match if and only if they are identical except for one additional character. Indicate the index where the difference occurs, or report failure if the two input strings do not differ in exactly one character.

Your task is to write a program that compares strings with one error. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Scheme provides the higher-order functions map, for-each and fold that operate on lists. In today’s exercise we will write versions of those functions that operate on strings:

(string-map proc str) applies proc to each character in str, replacing the character with the output of proc. proc takes a single character and returns a single character.

(string-for-each proc str) applies proc to each character in str; the function is executed only for its side-effects. proc takes a single character and returns nothing.

(string-fold proc base str) calls function (proc base c) on each character of str, working left to right, accumulating the result in base as it goes. proc takes a base of any type, and a character, and returns a value of the same type as base. (string-fold-right proc base str) is the same, except that it works from right to left.

Your task is to implement these four functions in the language of your choice. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The Shannon entropy of a file is a measure of the information content in the file; higher entropy implies more information. Shannon entropy is computed as H = -1 * sum(p_i * log₂(p_i)) where p_i is the frequency of each symbol i in the input (frequency is the percentage of the total number of symbols). Shannon entropy is just one facet of the study of information theory, which is fundamental to computer science.

Your task is to compute the Shannon entropy of a file. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

There has been much ado recently about a law-enforcement backdoor to encryption that would enable authorized access to private encrypted communications: FBI director James Comey and British Prime Minister David Cameron have both come out strongly in favor of an encryption backdoor as a tool in the fight against terrorists, while the EFF and cryptography experts are uniformly against the proposal. Today’s exercise looks at a way that an encryption backdoor can be added to the RSA cryptosystem.

Let’s start by reviewing how RSA works, as we have studied it in a previous exercise. Two large primes p and q are chosen at random; their product n is the modulus of the cryptosystem, and the totient φ(pq) of n is (p−1) × (q−1). Then two keys are chosen, the encryption key e and the decryption key d such that de ≡ 1 (mod φ(pq)) and gcd(e, φ(pq)) = 1. Then a message m, encoded as an integer on the range 0 < m < n, is encrypted as m^e (mod n) and the resulting ciphertext c is decrypted as c^d (mod n). In practice, e is usually 2¹⁶+1 = 65537 (that choice simplifies the arithmetic involved in encryption and decryption), p and q are t-bit integers with t ∈ {512, 1024} bits, and there are algorithms that allow the message to be any length (not limited to n), though we won’t look at them here because they are arcane and not germane to the RSA backdoor.

The encryption backdoor is inserted in the key generation process. The backdoor key a is chosen as a random prime of length 3t/4 bits; also chosen are two random primes p‘ and q‘ of length t/4 bits. Then p is computed based on p‘ by the following algorithm:

1 [Initialize]: Set k ← p‘.
2 [Compute p]: Set p ← a × k + p’.
3 [Check primality]: If p is prime, return p.
4 [Try again]: Set k ← k + 1 and go to Step 2.

And likewise for q, which is computed based on q‘. This process must terminate by Dirichlet’s Theorem, which says that for integers a, b and x with a and b coprime, the arithmetic progression ax + b contains infinitely many prime numbers. Once you’ve computed p and q, the key generation and ciphering processes of the normal RSA algorithm are unchanged.

An attacker who doesn’t know the backdoor key a can read an encrypted message m only by factoring n, which is difficult; that’s the basis of the secrecy provided by the RSA system. But an attacker who knows the backdoor key a can factor n (mod a) as p‘ × q‘, recover p and q and thus the decryption key d, and thus read the message m. Factoring n (mod a) is very much easier than factoring n; for instance, if n is a 2048-bit semiprime, n (mod a) is only 512 bits, which can be factored by a single personal computer in a few months, or by an AWS cluster in a few days, or by the supercomputers in the basement of the NSA one morning before you finish your first donut.

In practice, the RSA backdoor would work like this: Each device that performs encryption, say an iPhone or Android tablet, has a unique MAC address or KEK key or serial number that is somehow converted to a backdoor key a that is also unique to the device. (If a single backdoor key a was used for all devices, it could be recovered by a method similar to this exercise.) The device generates backdoored keys on request, then sends encrypted messages in the normal way. When some police agency wants to read an encrypted message, they request warrants from a judge, seize the device, determine the backdoor key a, and perform the procedure described above.

Your task is to write programs that demonstrate the RSA backdoor. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Dobble is a French card game that uses 55 cards, each with 8 symbols; any pair of cards have exactly one symbol in common. The game is played by dealing one card to each player and placing the remaining cards face-up in the center of the table; the first player to spot the symbol that matches the top card on his pile to the top card on the central pile calls out the name of the symbol, then moves the top card from the central pile to the top of his own pile, and the game continues until all cards in the central pile have been claimed, with the winner being the player with the most cards.

Your task is to write a program that creates a suitable deck of cards, so that every pair of cards has exactly one symbol in common. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Since we haven’t done one for a while, today’s exercise is an interview question:

Given a matrix of cells containing 0 or 1, modify the matrix so all cells in the same row or column as a cell containing a 1 also contain a 1. For instance, the matrix below left should be converted to the matrix below right:

0 0 0 0 0    1 0 0 1 0
0 0 0 0 0    1 0 0 1 0
0 0 0 1 0    1 1 1 1 1
1 0 0 0 0    1 1 1 1 1
0 0 0 0 0    1 0 0 1 0

Your task is to write a program to fill-in a matrix as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Since we haven’t done one for a while, today’s exercise is an interview question from Career Cup:

Given a matrix of cells containing 0 or 1, modify the matrix so all cells in the same row or column as a cell containing a 1 also contain a 1. For instance, the matrix below left should be converted to the matrix below right:

0 0 0 0 0    1 0 0 1 0
0 0 0 0 0    1 0 0 1 0
0 0 0 1 0    1 1 1 1 1
1 0 0 0 0    1 1 1 1 1
0 0 0 0 0    1 0 0 1 0

Your task is to write a program to fill-in a matrix as described above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Although the prime numbers are fascinating in their own right, sometimes it is interesting and instructive to look at the gaps between successive prime numbers. For instance, here is a table that shows how the maximal prime gap grows:

2    1
3    2
7    4
23   6
89   8
113  14
523  18
887  20

At each step the table shows a prime number and the gap to the next prime number; for instance, at prime 7 the gap to the next prime number, 11, is 4. The table only shows those instances where the prime gap increases. Note that the increases are not steady; for instance, a gap of 14 appears before a gap of 10 or 12.

Your task is to write a program that creates the table shown above. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Two numbers are compatible if they have the same prime factors, though with possibly different multiplicities.

Your task is to write a program to determine if two numbers are compatible. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

The triangular numbers (A000217) are those numbers that can be formed by identical objects arranged in a triangle. For instance, 10 bowling pins can be formed in a triangle with sides of length 4, so the fourth triangular number is 10.

Your task is to write a program that computes the n th triangular number; what is the 63rd triangular number? When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2