Bulk Deleting Folders based on existing git repos

sdfsdfsdfsdf By evan on Feb 08, 2016

I have a system set up where testers can ‘check out’ a feature branch to test. It sets up a full web environment (at var/www/test/branch_name), for an arbitrary feature and customer. It works great, but a problem quickly arose where we had to manually delete stale test environments.

Since repeating something twice means automating it…

There’s a way to delete all folders except a and b.

shopt -s extglob
rm -rf !(folderA|folderB)

shopt lets you use !(a|b) to not rm a or b.

Then we need to get a list of folders to not delete; this command will get every branch, that starts with “test/”, remove the prepended , replace newlines with |, and remove the last |.

git branch | grep 'test/' | sed 's/\ \ //g' | tr '\n' '|' | sed s'/.$//'
test/FEAT-1|test/FEAT-2|test/FEAT-3|test/FEAT-4

to use that in a shell script,

DIR_KEEP=`git branch | grep 'test/' | sed 's/\ \ //g' | tr '\n' '|' | sed s'/.$//'`
shopt -s extglob
rm -rf !($DIR_KEEP)

In this case, it expands to

rm -rf !(test/FEAT-1|test/FEAT-2|test/FEAT-3|test/FEAT-4)

Success! Throw that on an hourly cron job and it will cull the test directories as the feature branches are merged and deleted.

Factoring large semi-primes

sdfsdfsdfsdf By evan on Jan 31, 2016

tl;dr a friend of mine mentioned this problem over beers, and neglected to tell me that it’s considered impossible (thanks). Me being me, I gave it a shot, and appear to have devised a legitimate attack on large semi-prime that is not dependent on their size.

Long story short, it’s easy to multiply x * y, but harder to get x and y from back out of the answer. At it’s most basic level, 7 * 5 = 35. Conversely 35 = x * y, solve for y. There can only be one valid answer if both factors are primes, and when both factors are primes the product is called a ‘semiprime

It’s asymptotic complexity. In short, it sucks to brute force. It’s easy for a 2 digit number, not so much for a 200 digit number. That ‘s why no one uses 2 bit RSA keys. This mathematical asymmetry  is the entire basis of RSA encryption.

Before we continue, let’s declare a few variables. p is the first prime, q is the second prime, pq is their product (and the semi-prime).

The most obvious speed-up is limiting the search space.

  • The p and q will never be even numbers.
  • p will always be greater than the square root of pq, and q will always be smaller.

At this point, the search gets a bit smaller. But it’s still huge. Taking some time to refactor the formula (and I skipped a step or two, I’ve lost my original notes though will try to recreate them at some point)

x = sqrt(pq+(n^2))
p = x – n
q = x + n 

We can simply increment x until p*q == pq.

A few examples;

x = sqrt(35+(1^2)) = 6
p = 6 – 1 = 5
q = 6 + 1 =  7
Then confirm the results.. (5*7 == 35) and we’re done!

x = sqrt(77 + (1^2)) // is not an integer. Stop.
x = sqrt(77+(2^2)) = 9
p = 9 – 2 = 7
q = 9 + 2 =  11
Then confirm the results.. (7*11 == 77) and we’re done!

We’re at this point effectively looping through half of the difference of the primes, which is a lot smaller space than every number ever. This algorithm can factor a 50 digit prime in milliseconds on a netbook. This algorithm is fastest when the numbers are closest together.

Since we know both x and n are integers, we can do the search the other way, as x changes slower than n, by reversing it we get a speedup.

We can rearrange this as

x = ceil(sqrt(pq))
n = sqrt(x^2 – pq)
n = sqrt(6^2 – pq)
n = sqrt(36-35)
n = sqrt(1)
n = 1, x = 6.

p = 6+/- 1 = 5, 7.

 

Obviously the bigger the numbers are, the greater the difference between them. Ironically, it’s recommended to use values of p and q which are relatively close together. Thus this may be a valid attack against an RSA key

It’s non-deterministic, and can be parallelized (give each machine a 100,000,000,000,000,000 digit range to search

The only further speedup I see is if there’s a way to solve for the next integer value of n. The limiting factor here is that it’s effectively approaching a linear search as x approaches infinity. It’s extremely fast until the slope straightens out.

I’ve yet to come up with something so throwing this algorithm out there to see if anyone else can take it that last step.

 

UPDATE: Looking into it more, it’s a massive speedup in a small field, but not a large field, as it approaches a linear search of the difference between primes as x approaches infinity. This is fine for a 50 digit semiprime, but not a 200.

Tor Rate Limiting

sdfsdfsdfsdf By evan on Jan 31, 2016

If you know much about Tor, you know that all connections come from localhost. Even though it’s old news (I first heard about this a year ago) it has come up in the news recently.

It reminded me of a proof of concept I wrote for rate limiting hidden services, or alternatively, any service where you can’t distinguish users. Basically, you have them prove they did some amount of work (and therefore spent a certain amount of time between requests)

Factoring a semiprime, for example. It’s slow, which is why it is the basis of RSA encryption. More on that in the near future 😉

Full source at github

Update (Feb 15): There’s now another version of this concept available, which operates more similarly to bitcoin.

exifdetector

sdfsdfsdfsdf By evan on Mar 24, 2015

https://github.com/evandentremont/exifdetector

Built a exif detector. Kind of like a metal detector for geotagged images. Those that have data are circled in green. Those that don’t are circled in red.

Consider it a proof of concept. The lat/lng and a google maps link are logged to the console.

Bootstrap does not fit wordpress eh?

sdfsdfsdfsdf By evan on Dec 19, 2014

Then you’re doing it wrong.

The only thing that’s kind of screwy is the main nav. Apart from that, it’s no worse than any other front end framework, and better in a lot of ways.

Of course, I could be biased. I need to rewrite that theme to take advantage of LESS.

Dyslexia Chrome Plugin

sdfsdfsdfsdf By evan on Aug 25, 2014

Screen Shot 2014-08-25 at 6.52.30 PMNoticed a friend joking back and forth earlier about the ALS ice bucket challenge with of his with dyslexia. As soon as I heard that, I remembered having done a site a few years back  and asked him if the opendyslexia (more…)

Kijiji Unsold Plugin

sdfsdfsdfsdf By evan on Aug 04, 2014

kijiji_logo1I’ve been getting pretty frustrated with kijiji recently. One thing that keeps coming up is people writing “sold” in the title rather than actually deleting the ad. Why? I have no idea. Perhaps they think people (more…)

WordPress Chart Plugin

sdfsdfsdfsdf By evan on May 07, 2014

Screen-Shot-2014-05-07-at-11.50.17-AMI hadn’t been able to find a decent plugin to create charts in WordPress, so I wrote my own.

It uses HandsOnTable for the backend, to provide an excel-like editor, and Charts.js for the front end.

Long story short, (more…)

Watermarking an image

sdfsdfsdfsdf By evan on Feb 15, 2014

Note: This is a post from my old website, I came across it today and it’s still relevant.

Let’s suppose you have a ton of images that you want to protect from being copied.

The obvious solution is (more…)

Interlaced PNG’s

sdfsdfsdfsdf By evan on Jan 12, 2014

images (1)Browsing the internet the other day, I came across the “Interlaced PNG” format. This was apparently designed about 15 years ago when internet connections were much slower. As connection speeds get faster, there’s been a trend (more…)