3

I've come across this page about partial passwords, and I am having difficulty trying to understand the polynomial equations in there. I can understand basic algebra but this page's explanation is just not clear for me.

The variables are:
p1,p2,p3...pk  : the letters of password P
K : unique secret key
N : number of letters to ask everytime
R1,R2, R3...R(N-1) : random numbers
x : the order of the character/letter

My questions are:

  1. How are $y_1, y_2, y_3,\ldots,y_{N-1}$ to be calculated if $y = K+R_1 x + R_2 x^2 + ... + R_{N-1}x^{N-1}$?
  2. How is $s_k=(y_k-p_k)$ to be calculated if $p_k$ is a letter or character?

For the polynomial equation given : $K' = \sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)}$

  1. How is the value of j derived for each letter?
  2. In the substitution, $\prod_j$ values seem different in the 1st and 2nd instances:

    $$\sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)}K '= y_2\left(3 \frac{4}{(2-3)(2-4)} \right) + y_3 \left(2 \frac{4}{(3-2)(3-4)} \right) + y_4 \left(2 \frac{3}{(4-2)(4-3)} \right)$$

Would greatly appreciate if someone with better mathematical understanding could explain to me those questions clearly.

Peter Taylor
  • 13,425
  • 2
  • @Peter Taylor : Unfortunately no. Thanks for the link, for editing my question and for giving it a name. I found a tutorial as well : http://nm.mathforcollege.com/topics/lagrange_method.html I understand the summation symbol, but not the other symbol ∏j. I'm gonna read the tutorial, but could you please point me in the right direction with regards to my questions based on your understanding? – Noble_Bright_Life May 07 '13 at 12:06

1 Answers1

3

First, a bit of background. What they're doing here is based on Shamir's secret sharing. This is usually understood as a way of sharing a secret number between people so that none of them know it, but they can collaborate to find it out. E.g. suppose the nuclear launch code is to be shared between 5 generals in such a way that any 3 of them can launch the missiles. We rely on the basic property of polynomials that $n$ distinct points uniquely define an order $n-1$ polynomial. E.g. two points define a straight line, three points define a quadratic, 4 points define a cubic. So since we want 3 generals to collaborate and launch the missile, we choose a random quadratic $P$ such that $P(0)$ is our secret. Then we evaluate $P$ at 5 non-zero $x$-values and give a different $(x, P(x))$ pair to each general.

If you haven't understood that, read it again.

I've said that we rely on the fact that $n$ distinct points uniquely define an order $n-1$ polynomial, but I haven't said how to find that polynomial. If you're familiar with simultaneous equations then you should be able to see that one way of doing it is to treat each point as an equation in the coefficients (e.g. for the quadratic $y(x) = ax^2 + bx + c$, the point $(3, 7)$ is the equation $7 = 3^2a + 3b + c$) and solve them by any suitable method. However, it's quicker to use Lagrange interpolation, although less quick to understand why it works. I won't explain that in full in this answer - the link I gave in a comment should be a good starting point, and if you have specific questions about it then you can ask them separately.

Ok, onto the specific questions you asked above:

  1. $y_1$ is defined in point B4 as a shorthand notation for $y(1)$, and since $y = K+R_1 x + R_2 x^2 + \ldots + R_{N-1}x^{N-1}$ that means that $y_1 = K+R_1 + R_2 + \ldots + R_{N-1}$, $y_2 = K+2 R_1 + 4 R_2 + \ldots + 2^{N-1}R_{N-1}$, etc.

  2. We define a numeric value for each possible letter. If you're doing a worked example you might want to use $A=1, B=2, \ldots Z=26$. For "real world" implementations there are various standard character sets which are used for this; see e.g. UCS. For reasons going back to the (relatively) early days of computing, most of the character sets which are used for text in Western European languages languages have $A=65, B=66, \ldots$

  3. Your comment clarifies that you're familiar with the summation symbol $\sum$, but not with $\prod$. This upper-case Pi symbol is usually read as "product" and is like $\sum$ except that it multiplies rather than adding. So just as the $i$ in $\sum_i$ is a bound variable which runs over a range understood from context, the $j$ in $\prod_j$ is a bound variable which runs over a range understood from context. Here the explanation you're reading assumes familiarity with Lagrange interpolation, which supplies the context necessary to read it as "each $j$ from $1$ to $N$ which is not equal to $i$". Actually that's also spelt out as

    where i and j run over i1, i2, ..., iN (step 1), and j skips the actual selected i.

  4. So with that context we can expand out a bit. In the worked example, $N=3$, and the values $i$ and $j$ can take are $2,3,4$ so $$\begin{eqnarray} K^\prime & = & \sum_i y_i \frac{\prod_j (j)}{\prod_j (i-j)} \\ & = & y_2 \frac{\prod_{j \ne 2} (j)}{\prod_{j \ne 2} (2-j)} + y_3 \frac{\prod_{j \ne 3} (j)}{\prod_{j \ne 3} (3-j)} + y_4 \frac{\prod_{j \ne 4} (j)}{\prod_{j \ne 4} (4-j)} \\ & = & y_2 \frac{3\cdot 4}{(2-3)(2-4)} + y_3 \frac{2\cdot 4}{(3-2)(3-4)} + y_4 \frac{2\cdot 3}{(4-2)(4-3)} \end{eqnarray}$$ I would prefer to write it instead as $$\begin{eqnarray} K^\prime & = & \sum_i y_i \prod_{j \ne i} \frac{j}{i-j} \\ & = & \left( y_2 \cdot\frac{3}{2-3} \cdot\frac{4}{2-4} \right) + \left( y_3 \cdot\frac{2}{3-2}\cdot\frac{4}{3-4} \right) + \left( y_4 \cdot\frac{2}{4-2}\cdot\frac{3}{4-3} \right) \end{eqnarray}$$

Peter Taylor
  • 13,425
  • That's a really comprehensive explanation. Thanks! I think I now have a quite good grasp of this, though not robust yet. Some clarifications : #1. Does it follow then that the general formula for y is yz = K + Z1R1 +....+ ZN-1RN-1 ? (how do I format the math symbols/subscripts/superscripts to display properly?)

    #2. Got It. 65 is the Decimal ASCII equivalent of A.

    #3&4. For ∏j≠2 in y2 for example, why is the substitution not (34)2 / (34)(2-4)? From another angle, why is the numerator not multiplied with 2 (the j) in your expansion, and the denominator not (34) but (3-4)?

    – Noble_Bright_Life May 07 '13 at 16:28
  • Sorry, I made a mistake for #3&4. Should read "In y2 for example, why is the substitution not (34)2 / (34)(2-4)? From another angle, why is the numerator not multiplied with 2 (the j) in your expansion, and the denominator not (34) but (2-3) for ∏j≠2 ?" – Noble_Bright_Life May 07 '13 at 16:46
  • 1
    @AxenZhyrkhinsky, http://meta.math.stackexchange.com/q/5020/5676 is a good introduction to the mathematical markup. With appropriate sub- and superscripts your formula for $y_z$ is correct. For $\prod_{j \ne 2}$, the $j$ is not 2. It takes the (relevant) values which aren't 2: i.e. 3 and 4. If we define $L(a, b) = b/(a-b)$ then (using my preferred, shorter, formulation) $K^\prime = \sum_i y_i \prod_{j \ne i}L(i,j) = y_2 L(2,3) L(2,4) + y_3 L(3,2) L(3,4) + y_4 L(4,2) L(4,3)$. (It's quite natural that the product should be over $j\ne i$ because if $j=i$ we get division by zero). – Peter Taylor May 07 '13 at 20:38
  • Got it! I was thinking that ∏j≠i is to be substituted per symbol. Its to be expanded, using multiplication, like summation is to be expanded by addition. Thanks a lot for your patience and sharing your knowledge :) All the best. – Noble_Bright_Life May 08 '13 at 05:40