Shamir's secret sharing - graph issues

[simlei]

In 77f9154 under Linux/GTK3, I am not seeing any graph.

With the changes in https://github.com/simlei/crypto/commit/3f48a73d4f8368f5d6826efebb477e58f9ddbccb I am seeing a graph. The reason for it not to draw anything must be in using different GC (graphical context) objects with different scaling. This does seem to work under Windows, but not under Linux/GTK3/Cairo.

The newly obtained results on that test branch, however, look like this:

Under windows we have had similar problems. @grthor, do you remember something about that and how it was solved?

I suspect the jagged edges to result from line-with zero which is indicated as the "fastest method": Compare javadoc here: https://help.eclipse.org/2019-12/nftopic/org.eclipse.platform.doc.isv/reference/api/org/eclipse/swt/graphics/GC.html#setLineWidth(int)

If I explicitely setLineWidth(1) e.g., I am getting a smooth, albeit way too thick curve.

And the reason for that is, I suspect, the per-GC-scaling (setTransformation) on multiple GC. When the scaling is too high, the line gets too thick.

Since solving the line thickness easily would require SWT to accept floating-point line thickness -- which it does not -- the only alternative is to scale the curve mathematically, in image space.

I.e. in the code, the polynomial coefficients have to be adapted to the pixel space of the image when rendering. This is for now left to the eager reader as an exercise and may be explored in further versions of this issue :)

First off, though, I need consistent behavior across Linux/GTK3 + Windows.

[simlei]

After cross platform stability is given, these improvements should be implemented:

• [x] As shown in the online help it should be a smooth graph, but here it has edges. And the checked shares should be on the graph and not besides it.
• [x] x-axis labels are cut off (see below)
• [x] More spaced-out y-axis labels (half the frequency e.g.)

[simlei]

It looks like this as of #293 . At least on one Windows VM and on one Linux machine this looks good now I think.

@be4 if you could take a look at whether the reconstructed graphs with too few shares (red lines) are mathematically correct, that would be a great help. Intuitively, I think those lines should go through all points that represent a share, but on my system, they seem to not always do that. However, when enough shares match, the reconstructed (green) graph always perfectly matches the original graph:

The red line seems to be plotted just according to the formula (9x+4, crossing the y axis at y=4)

[grthor]

I don't want to disappoint you, but under Windows with 150% screen zoom the x-axis labels are still cut off and the y-axis labels are still too close together.

I just checked out your changes, so I should have tested the latest version.

The graph as it looks much better now.

[Leikani]

In the frist sample we have 4 shares, all belong to the blue curve.

Then the two light red points are selected (and the dark red pints are not selected). So the red curve (line) should go through these 2 light red points -- I have no idea why the red line is somewhere else.

In the 2nd screenshot the green curve is correct: the 3 selected light red points are on the curve, and the dark red one also.

Best regards

Am 09.04.2020 um 16:56 schrieb Simon Leischnig:

It looks like this as of #293 . At least on one Windows VM and on one Linux machine this looks good now I think.

@be4 if you could take a look at whether the reconstructed graphs with too few shares (red lines) are mathematically correct, that would be a great help. Intuitively, I think those lines should go through all points that represent a share, but on my system, they seem to not always do that. However, when enough shares match, the reconstructed (green) graph always perfectly matches the original graph:

[simlei]

In the frist sample we have 4 shares, all belong to the blue curve. Then the two light red points are selected (and the dark red pints are not selected). So the red curve (line) should go through these 2 light red points -- I have no idea why the red line is somewhere else. In the 2nd screenshot the green curve is correct: the 3 selected light red points are on the curve, and the dark red one also. Best regards

Thanks! As I already noted, the red line perfectly resembles P'(x) as shown in the GUI. If it is certain that the reconstruction must include the share points, then this means the plug-in has a bug in calculating the correct reconstructed polynom. I will look into that later as it means debugging some polynome divisions.

[simlei]

I don't want to disappoint you, but under Windows with 150% screen zoom the x-axis labels are still cut off and the y-axis labels are still too close together.

I just checked out your changes, so I should have tested the latest version.

The graph as it looks much better now.

Thanks! OK, looks like higher-DPI displays are messing with us here. I would need to get the DPI scaling factor from somewhere. Looking into it.

[simlei]

My way to solve the problem is to use the font height to calculate the distance between the labels. The font height depends on the DPI and the screen zoom.

gc.getFontMetrics().getHeight() gets you the font height

OK, that seems to be the best indirect way :) I'll try to get that into the next weekly build at least

[simlei]

Axis labels now scale & occupy space according to the font metrics which should work for all display managers that scale fonts.

y Axis label distances get chosen automatically so that they 1) appear every 2.5 times font height at minimum 2) are distributed/spaced out in units in one of the following periods: {1, 2, 5, 10, 20, 50, 100, 200, 500, 1000}

[simlei]

Leikani wrote Apr 9, 5:31 PM:

In the frist sample we have 4 shares, all belong to the blue curve. Then the two light red points are selected (and the dark red pints are not selected). So the red curve (line) should go through these 2 light red points -- I have no idea why the red line is somewhere else. In the 2nd screenshot the green curve is correct: the 3 selected light red points are on the curve, and the dark red one also. Best regards

Simon Leischnig wrote Apr 9, 5:41 PM:

Thanks! As I already noted, the red line perfectly resembles P'(x) as shown in the GUI. If it is certain that the reconstruction must include the share points, then this means the plug-in has a bug in calculating the correct reconstructed polynom. I will look into that later as it means debugging some polynome divisions.

OK, I investigated this. I could find no apparent fault at first. Looking into lagrange interpolation, it became apparent:

Rather than requiring to pass the share points before the modulo operation, the lagrange interpolation is only required to pass such a point in modulo space. That the correctly reconstructed curve passes the points before applying modulo is at the core of the algorithms function.

Thus, the plug-in works correctly, but the visualization of the reconstructed curve is as-is not very informative. While trying to test it and make this more apparent, I experimented with a visual of the share points:

Insufficient shares (note the light blue points are the known shares but with all extrapolations out of modulo space)

Sufficient shares

These additional points are not in the weekly-built plugin though, as this was rather a hot take at the problem and would need some fleshing out as for the presentation.

[simlei]

@be4 the fixed version w.r.t. DPI scaling should be included in the upcoming weekly build for testing and taking screenshots

[simlei]

• [x] include some form of the modulus ring visualization (idea: label polynom-dot and reconstructed dot on the graph)

[simlei]

I think this should more or less do it :) Hover balloon for the highlighted dot is not shown due to screenshot tool being buggy.