text:
Cops and Robbers: Reverse Regex Golf

Note: This challenge is now closed. Any future cops' submission will not be considered for the accepted answer. This is to ensure that no one can post a very simple regex in the future that only remains uncracked because no one is interested in the challenge any more.

The Cops' Challenge
You are to write a short, obfuscated regex, satisfying the following spec:

You may choose any flavour that is freely testable online. There's a good list of online testers over on StackOverflow. In particular, Regex101 should be good to get you started, as it supports PCRE, ECMAScript and Python flavours. You can increase the timeout limit by clicking on the wrench in the top right corner if necessary. Please include the tester you choose in your answer.
If no suitable tester is available for your flavour of choice, you may also use an online interpreter like ideone and write a little script in the host language which people can use to test your submission.
You may use any feature of that flavour, which does not directly invoke the host language (like Perl's code evaluation features).
Likewise, you may use any modifiers (if your flavour has them), unless they result in code evaluation.
Your regex must accept at least one string S and reject at least one string T, each of which is at least 16 and not more than 256 characters in length, in a reasonable amount of time (not significantly longer than a minute). S and T may contain Unicode characters that aren't ASCII, as long as there's a way to enter them into the online tester. Any such pair of strings will be a key to your submission.
Your regex may take arbitrarily long on any other input.

The core of the challenge is to craft a regex whose key is hard to find. That is, it should either be hard to tell which string it doesn't match or which string it matches (or potentially even both if the regex takes days to finish on all but the key's strings).
The Robbers' Challenge
All users, including those who have submitted their own regex(es), are encouraged to "crack" other submissions. A submission is cracked when one of its keys is posted in the associated comments section.
Important: Make sure that both strings you post are between 16 and 256 characters inclusive, even if almost any string could be used be used for one part of the key.
If a submission persists for 72 hours without being modified or cracked, the author may reveal a valid key by editing it into a spoiler-tag in his answer. This will make his answer "safe", i.e. it can no longer be cracked.
Only one cracking attempt per submission per user is permitted. For example, if I submit to user X: "Your key is 0123456789abcdef/fedcba9876543210." and I'm wrong, user X will disclaim my guess as incorrect and I will no longer be able to submit additional guesses for that submission, but I can still crack other submissions (and others can still crack that submission).
Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited or deleted. If an author wishes to submit a new regex, (s)he should do so in a separate answer.
Do not crack your own submission!
Note: For long strings in the comments without spaces, SE inserts manual line breaks in the form of two Unicode characters. So if you post a key in backticks which is so long that it line-wraps between non-space characters, it won't be possible to copy the key straight back out into a regex tester. In this case, please provide a permalink to the relevant regex tester with the cop's regex and your key - most testers include this feature.
Scoring
A cop's score will be the size of their regex in bytes (pattern plus modifiers, potential delimiters are not counted), provided that it hasn't been cracked. The lowest score of a "safe" submission will win.
A robber's score will be the number of submissions they cracked. In the event of a tie, the total byte size of submissions they cracked will be used a tie-breaker. Here, highest byte count wins.
As stated above, any cop may participate as a robber and vice-versa.
I will maintain separate leaderboards for the two parts of the challenge.
Leaderboards
Last update: 19/10/2014, 20:33 UTC
Cops:
Submissions in italics are not yet safe.

nneonneo, 841 bytes
Wumpus Q. Wumbley, 10,602 bytes
Sp3000, 52,506 bytes
user23013, 53,884 bytes
nneonneo, 656,813 bytes

Robbers:

user23013, Cracked: 11, Total Size:
733 +
30 +
2,447 +
71 +
109 + 121 +
97 +
60 +
141 +
200,127 +
7,563 = 211,499 bytes
nneonneo, Cracked: 10, Total Size:
4,842 +
12,371 +
150 +
3,571 +
96 +
168 +
395 +
1,043 +
458 +
17,372 = 40,466 bytes
Wumpus Q. Wumbley, Cracked: 6, Total Size:
22 +
24 +
158 +
32 +
145,245 +
145,475 = 290,956 bytes
Dennis, Cracked: 2, Total Size:
70 +
73 = 143 bytes
harius, Cracked: 1, Total Size: 9,998 bytes
g.rocket, Cracked: 1, Total Size: 721 bytes
stokastic, Cracked: 1, Total Size: 211 bytes
Sp3000, Cracked: 1, Total Size: 133 bytes
TwiNight, Cracked: 1, Total Size: 39 bytes

I wonder how many lines of code we've collectively written constructing these puzzles and attempting to solve them... and whether it would be worthwhile to collect it all and stick it on github when we're done. Everybody could contribute whatever they've got (encoders, decoders, solvers both successful and unsuccessful), as-is, uncommented and hackish though they may be. With a README if you feel like it. It would be like our conference proceedings.

While there aren't any new answers being posted anymore, it may be worth "closing" the question at some point. Otherwise, it may be possible for someone to answer when the interest has died down, and stand uncontested for a longer period.

@nneonneo Hm, I don't usually like to close my challenges, but in this case it may be a good idea. I even think the last 3 entries already benefited from getting less attention. I'll set a deadline for Friday.

@MartinBüttner: I think it will have to be standard for cops & robbers challenges to have an expiry date. Challenges only stay interesting for so long. (For the record, this challenge is probably still my personal favorite, but I may be biased in that opinion :)

.NET regex, 841 bytes [Safe!]
Now that I've got a safe entry, lets see how small I can make the regex!
^(?<a>){53}((0(((?<-a>)(?<A>){7}|){997}((?<-b>)(?<B>){7}|){997}((?<-c>)(?<C>){7}|){997}((?<-d>)(?<D>){7}|){997}((?<-e>)(?<E>){7}|){997}((?<-f>)(?<F>){7}|){997}((?<-g>)(?<G>){7}|){997}(?<A>){5})|1(((?<-a>)(?<A>){3}|){997}((?<-b>)(?<B>){3}|){997}((?<-c>)(?<C>){3}|){997}((?<-d>)(?<D>){3}|){997}((?<-e>)(?<E>){3}|){997}((?<-f>)(?<F>){3}|){997}((?<-g>)(?<G>){3}|){997}(?<A>)))((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}((?<-G>){997}|){9}((?<-G>)(?<g>)|){997}){256}$(?<-a>){615}(?(a)(?!))(?<-b>){59}(?(b)(?!))(?<-c>){649}(?(c)(?!))(?<-d>){712}(?(d)(?!))(?<-e>){923}(?(e)(?!))(?<-f>){263}(?(f)(?!))(?<-g>){506}(?(g)(?!))

Prettified:
^(?<a>){53}
(
    (0(
        ((?<-a>)(?<A>){7}|){997}
        ((?<-b>)(?<B>){7}|){997}
        ((?<-c>)(?<C>){7}|){997}
        ((?<-d>)(?<D>){7}|){997}
        ((?<-e>)(?<E>){7}|){997}
        ((?<-f>)(?<F>){7}|){997}
        ((?<-g>)(?<G>){7}|){997}
        (?<A>){5})
    |1(
        ((?<-a>)(?<A>){3}|){997}
        ((?<-b>)(?<B>){3}|){997}
        ((?<-c>)(?<C>){3}|){997}
        ((?<-d>)(?<D>){3}|){997}
        ((?<-e>)(?<E>){3}|){997}
        ((?<-f>)(?<F>){3}|){997}
        ((?<-g>)(?<G>){3}|){997}
        (?<A>))
    )
    ((?<-A>){997}(?<B>)|){9}((?<-A>)(?<a>)|){997}
    ((?<-B>){997}(?<C>)|){9}((?<-B>)(?<b>)|){997}
    ((?<-C>){997}(?<D>)|){9}((?<-C>)(?<c>)|){997}
    ((?<-D>){997}(?<E>)|){9}((?<-D>)(?<d>)|){997}
    ((?<-E>){997}(?<F>)|){9}((?<-E>)(?<e>)|){997}
    ((?<-F>){997}(?<G>)|){9}((?<-F>)(?<f>)|){997}
    ((?<-G>){997}|){9}      ((?<-G>)(?<g>)|){997}
){256}$

(?<-a>){615}(?(a)(?!))
(?<-b>){59}(?(b)(?!))
(?<-c>){649}(?(c)(?!))
(?<-d>){712}(?(d)(?!))
(?<-e>){923}(?(e)(?!))
(?<-f>){263}(?(f)(?!))
(?<-g>){506}(?(g)(?!))

Features:

Short, 841 bytes
Golfed and written by hand
Not known to encode an NP-hard problem
Times out on most invalid input :)
Tested on http://regexhero.net/tester/, takes ~5 seconds for the valid input

Thanks to Sp3000 and user23013 for cluing me in to .NET regex.

After 72 hours, I am revealing the key to make this submission safe.
Match:
1110111111110010000110011000001011011110101111000011101011110011001000000111111111001010000111100011111000000100011110110111001101011001000101111110010111100000000010110001111011011111100000011001101110011111011010100111011101111001110111010001111011000000

Non-match: Aren'tHashFunctionsFun?
Explanation:

 This regular expression implements a very simple and rather stupid hash function. The hash function computes a single integer x as output. x starts off equal to 53. It is adjusted based on each character encountered: if it sees a 0, it will set x = 7x + 5, and if it sees a 1, it will set x = 3x + 1. x is then reduced mod 9977. The final result is checked against a predefined constant; the regex fails to match if the hash value is not equal.

 Seven capture groups (a-g) are used to store the base-997 digits of x, with seven more capture groups (A-G) serving as temporary storage. I use the "balancing capture groups" extension of .NET regex to store integers in capture groups. Technically, the integer associated with each capture group is the number of unbalanced matches captured by that group; "capturing" an empty string using (?<X>) increments the number of captures, and "balancing" the group using (?<-X>) decrements the number of captures (which will cause a match failure if the group has no captures). Both can be repeated to add and subtract fixed constants.

 This hash algorithm is just one I cooked up in a hurry, and is the smallest hash algorithm I could come up with that seemed reasonably secure using only additions and multiplications. It's definitely not crypto-quality, and there are likely to be weaknesses which make it possible to find a collision in less than 9977/2 hash evaluations.

I had an idea... Then I gave up because I don't have 500+GB free space on my hard drive.

Seeing it now in 3 uncracked submissions, I'm officially registering my complete ignorance of the purpose of the construct (?<a>){53}. It appears to be capturing the empty pattern into named group a 53 times. So set a="" then repeat 52 more times? But I don't really know if (?< means the same thing in Microsoft's idea of a regexp. Their documentation fails to even mention it. If even a regexp contest ends with undocumented Microsoft extensions rolling over the unix people, my existence has no purpose.

It is a group capture that captures nothing 53 times. .NET has an extension called balancing group captures which is their answer to paren matching. Each named group acts like a stack, so (?<a>){53} pushes the empty string 53 times. You can pop the stack using (?<-a>). Hopefully now it is clear why this construct is so useful.

The documentation you want is http://msdn.microsoft.com/en-us/library/bs2twtah(v=vs.110).aspx.

@WumpusQ.Wumbley I'm the unix people who found this useful.

@WumpusQ.Wumbley For some more elaboration, there's a link in the spoiler of my own .NET answer.

if I google "perl regex syntax" or "perl regexp specification" or "perl regular expression manual" or "perl regex reference" the complete documentation of the perl regexp syntax is always among the top 3 links, sometimes outranked by perlreref (which tells you that perlre is the complete spec) and a wikipedia article. Same for python. In contrast, Microsoft puts some stuff on a separate page and doesn't link to it from the one titled "Regular Expression Syntax". sigh I've learned I should avoid contests that aren't explicitly unix-based; anger and sadness are the inevitable results.

@WumpusQ.Wumbley Because the page you have linked is the JScript regex, not the .NET one. And JScript doesn't have those features.

@WumpusQ.Wumbley MSDN has an entire page about grouping constructs. Which can be found from the quick reference. Which is the first hit for ".net regex reference", analogously to your Perl search term. (Same for "syntax", "manual" or "specification").

@MartinBüttner: Is this submission now safe? I think the 72 hours have elapsed.

@nneonneo It's safe as soon as you reveal the key. ;)

OK, was just checking to make sure the 72 hours had elapsed.

wondering what the solution is, and if you uncover key bar for new submissions is pretty high

It's just a randomly-generated string of 256 0s and 1s. I don't have the key on me here at work, or I'd post it right away.

@MartinBüttner: It is now safe.

@user23013: Now I'm curious: were you planning to meet-in-the-middle attack this hash function? How would that work, exactly?

@nneonneo Yes. And I'm still running the attack program which uses 280GB disk space. But I have lost half of the log file for stupid reasons. The rest doesn't contain a successful result. First make a guess of the first 186 bits (now i think 184 bits should be better, but only if I have a larger disk). Then list every possible result after the 221th bit (from both side). Discard half of them by checking a certain bit because I don't have so much space, and the CPU is faster than disk I/O.

@nneonneo Write them to about 400*2 different files (or faster equivalent, each with a big cache) according to certain bits. When everything is done, load the corresponding files of both side, sort them and check if I'm lucky and there is a number appeared in both files. Run the search program again to get the bits.

I tried a few times but it didn't work. Then I tried to "guess" first bits from the key you have revealed, it has returned exactly one solution. I think it isn't random enough to make this attack work.

@user23013: Do you mean that the hash algorithm is not sufficiently random? I can absolutely believe that; the algorithm produces an output that has a strong mathematical relationship to the input data. I'm surprised that this makes it harder to crack. To be honest, I thought that it would be cracked via some clever number-theory reversal.

@nneonneo I'm not sure. Maybe I'm just unlucky. If it isn't random, the attack can still be fixed by not hard-coding 186 bit guess, but try 2^35 random 221 bit strings. But I didn't think of this.

Basic Regex, 656813 bytes [safe!]
The regex to end all regexes. One final hurrah into the night.
Testable under PCRE, Perl, Python and many others.
bzip2'd and base64-encoded version on Pastebin: http://pastebin.com/9kprSWBn (Pastebin didn't want the raw version because it was too big).
To make sure you get the right regex, you can verify that its MD5 hash is
c121a7604c6f819d3805231c6241c4ef

or check that it begins with
^(?:.*[^!0-9@-Za-z].*|.{,255}|.{257,}|.[U-Za-z].{34}[12569@CDGHKLOPSTWXabefijmnqruvyz].{8}[02468@BDFHJLNPRTVXZbdfhjlnprtvxz].{210}

and ends with
.{56}[7-9@-DM-Tc-js-z].{121}[3-6A-DI-LQ-TYZabg-jo-rw-z].{28}[!0-9@-T].{48})$

The key is still a nice comfortable 256 bytes.
I tested this regex with Python, but note that this regex doesn't use any special features of Python. Indeed, with the exception of (?:) (as a grouping mechanism), it actually uses no special features of any regex engine at all: just basic character classes, repetitions, and anchoring. Thus, it should be testable in a great number of regular expression engines.
Well, actually, I can still crank the difficulty up, assuming someone doesn't just instantly solve the smaller problems...but I wager people will have trouble with a 1GB regex...

After 72 hours, this submission remains uncracked! Thus, I am now revealing the key to make the submission safe. This is the first safe submission, after over 30 submissions were cracked in a row by persistent robbers.
Match: Massive Regex Problem Survives The Night!
Non-match: rae4q9N4gMXG3QkjV1lvbfN!wI4unaqJtMXG9sqt2Tb!0eonbKx9yUt3xcZlUo5ZDilQO6Wfh25vixRzgWUDdiYgw7@J8LgYINiUzEsIjc1GPV1jpXqGcbS7JETMBAqGSlFC3ZOuCJroqcBeYQtOiEHRpmCM1ZPyRQg26F5Cf!5xthgWNiK!8q0mS7093XlRo7YJTgZUXHEN!tXXhER!Kenf8jRFGaWu6AoQpj!juLyMuUO5i0V5cz7knpDX0nsL
Regex explanation:

 The regex was generated from a "hard" 3SAT problem with a deliberately-introduced random solution. This problem was generated using the algorithm from [Jia, Moore & Strain, 2007]: "Generating Hard Satisfiable Formulas by Hiding Solutions Deceptively". Six boolean variables are packed into each byte of the key, for a total of 1536 variables.
 The regex itself is quite simple: it expresses each of 7680 3SAT clauses as a an inverted condition (by de Morgan's laws), and matches any string that does not meet one of the 3SAT clauses. Therefore, the key is a string which does not match the regex, i.e. one that satisfies every one of the clauses.

So, I just tried loading a 60MB regex into Python. Predictably, it wasn't too happy. It took several minutes to compile, but the cool part is that it was nearly instant to answer queries. I suspect loading a 1GB regex into Python will take a few hours to compile...

minisat is running. The last one took 2 hours and this one is twice as big so I'm worried. It would be really easy to carve this up and make it a distributed crack...

Or not so easy. Based on my first attempt to carve it down to solvable size, we'll need about 2**61 CPUs to finish in time.

tried to post the raw regex on gist.github.com already?

seems that you got a pesky good one :)

The challenge begins, "You are to write a short, obfuscated regex" (emphasis added)

@Ypnypn The challenge so far has been to even get any uncrackable regex on the board - this one looks like it'll be the first to break that barrier though :)

Congratulations on being the first one to make it through the 72 hours after 34 cracked answers! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked.

@MartinBüttner: Thanks! I have done so. Now I have to go off and try some of these other NP-hard regex problems...

I think this could definitely use a blog post or something, I'd like to hear more about how to encode problems like these into regexes.

ECMAScript (10602 bytes)
(Language note: I see a lot of posts labeled ruby, or python, or whatever, when they really don't use any language-specific features. This one only requires (?!...) and (?=...) on top of POSIX ERE with backreferences. Those features are probably in your favorite language's regexp engine, so don't be discouraged from trying the challenge because I chose to use the javascript online tester.)
Just a little bit of fun, not as computationally difficult as some of the others.
^(?!(.).*\1.|.+(.).*\2)(?=(.))(?=(((?![ҁѧѦЩ]{2}).)*(?=[ҁѧѦЩ]{2}).){2}(?!.*[ЩѦҁѧ]{2}))(?=(((?![ɿqԼϚ]{2}).)*(?=[ϚqԼɿ]{2}).){2}(?!.*[ԼϚɿq]{2}))(?=((?![ϼλҡՄ]{2}).)*(?=[ҡλϼՄ]{2}).(?!.*[Մλϼҡ]{2}))(?=(((?![ʯֆɎF]{2}).)*(?=[FֆʯɎ]{2}).){2}(?!.*[FɎֆʯ]{2}))(?=(((?![AɔbУ]{2}).)*(?=[ɔbAУ]{2}).){3}(?!.*[ɔAbУ]{2}))(?=(((?![ʈͽՄɒ]{2}).)*(?=[ͽՄɒʈ]{2}).){2}(?!.*[ͽՄɒʈ]{2}))(?=(((?![ϙшѭϢ]{2}).)*(?=[Ϣϙѭш]{2}).){2}(?!.*[ѭшϙϢ]{2}))(?=(((?![ՐɏƋѠ]{2}).)*(?=[ƋՐɏѠ]{2}).){2}(?!.*[ѠƋՐɏ]{2}))(?=(((?![Жտʓo]{2}).)*(?=[Жտʓo]{2}).){2}(?!.*[Жʓտo]{2}))(?=(((?![ƆʙƸM]{2}).)*(?=[ƆʙMƸ]{2}).){2}(?!.*[ƆʙMƸ]{2}))(?=(((?![dNѤѯ]{2}).)*(?=[ѤѯNd]{2}).){2}(?!.*[ѤѯdN]{2}))(?=(((?![ҎvȵҜ]{2}).)*(?=[vҜȵҎ]{2}).){2}(?!.*[ҎvҜȵ]{2}))(?=(((?![ҹɀҀҤ]{2}).)*(?=[ɀҤҀҹ]{2}).){2}(?!.*[ҹҤҀɀ]{2}))(?=(((?![OɄfC]{2}).)*(?=[fOɄC]{2}).){3}(?!.*[ɄOfC]{2}))(?=((?![ǷϗЋԒ]{2}).)*(?=[ЋϗԒǷ]{2}).(?!.*[ԒϗЋǷ]{2}))(?=((?![էҹϞҀ]{2}).)*(?=[ҹҀէϞ]{2}).(?!.*[ϞէҹҀ]{2}))(?=(((?![QԶϧk]{2}).)*(?=[QkϧԶ]{2}).){2}(?!.*[ϧԶkQ]{2}))(?=(((?![cիYt]{2}).)*(?=[իYct]{2}).){2}(?!.*[tcYի]{2}))(?=(((?![ɐҷCɄ]{2}).)*(?=[CɄɐҷ]{2}).){3}(?!.*[CҷɐɄ]{2}))(?=(((?![ҥմѾϢ]{2}).)*(?=[ϢѾմҥ]{2}).){2}(?!.*[մϢѾҥ]{2}))(?=((?![Ϛǝjɰ]{2}).)*(?=[Ϛǝjɰ]{2}).(?!.*[jɰϚǝ]{2}))(?=((?![ϭBѾҸ]{2}).)*(?=[ѾҸϭB]{2}).(?!.*[ѾҸBϭ]{2}))(?=((?![ϼλyՎ]{2}).)*(?=[λՎyϼ]{2}).(?!.*[λՎyϼ]{2}))(?=((?![MԋƆƻ]{2}).)*(?=[ƻƆԋM]{2}).(?!.*[MƆԋƻ]{2}))(?=(((?![uԳƎȺ]{2}).)*(?=[uԳƎȺ]{2}).){3}(?!.*[ȺƎuԳ]{2}))(?=((?![ɂƐϣq]{2}).)*(?=[qϣƐɂ]{2}).(?!.*[ɂƐϣq]{2}))(?=(((?![ϫճωƺ]{2}).)*(?=[ωϫճƺ]{2}).){2}(?!.*[ճƺϫω]{2}))(?=((?![ζɏΞƋ]{2}).)*(?=[ɏƋζΞ]{2}).(?!.*[ɏƋζΞ]{2}))(?=(((?![Ӄxԏϣ]{2}).)*(?=[Ӄxԏϣ]{2}).){2}(?!.*[ԏxϣӃ]{2}))(?=(((?![ԈʄʫԻ]{2}).)*(?=[ԻʄԈʫ]{2}).){2}(?!.*[ʫԈԻʄ]{2}))(?=(((?![ɒէƣʈ]{2}).)*(?=[ʈɒէƣ]{2}).){2}(?!.*[ʈƣɒէ]{2}))(?=(((?![Ϥϟƺϫ]{2}).)*(?=[Ϥϫϟƺ]{2}).){3}(?!.*[ƺϫϤϟ]{2}))(?=((?![ɋȡþͼ]{2}).)*(?=[ȡþͼɋ]{2}).(?!.*[þͼȡɋ]{2}))(?=((?![ҡʈԄՄ]{2}).)*(?=[ʈԄՄҡ]{2}).(?!.*[ՄԄҡʈ]{2}))(?=(((?![ʌkȿՌ]{2}).)*(?=[Ռȿkʌ]{2}).){3}(?!.*[kՌȿʌ]{2}))(?=(((?![gǝժʮ]{2}).)*(?=[ǝgʮժ]{2}).){2}(?!.*[gǝʮժ]{2}))(?=((?![ɧƸȝՊ]{2}).)*(?=[ƸɧȝՊ]{2}).(?!.*[ՊȝɧƸ]{2}))(?=(((?![ɜȶʟɀ]{2}).)*(?=[ɀȶʟɜ]{2}).){3}(?!.*[ȶɀʟɜ]{2}))(?=((?![ƅѿOf]{2}).)*(?=[ѿfƅO]{2}).(?!.*[Oѿfƅ]{2}))(?=(((?![GҠƪԅ]{2}).)*(?=[ҠGԅƪ]{2}).){2}(?!.*[GԅƪҠ]{2}))(?=(((?![Һӻѩͽ]{2}).)*(?=[ӻͽҺѩ]{2}).){2}(?!.*[ͽҺѩӻ]{2}))(?=(((?![ʊLՅϪ]{2}).)*(?=[ՅʊLϪ]{2}).){3}(?!.*[LʊϪՅ]{2}))(?=(((?![ɅՈƪԅ]{2}).)*(?=[ƪԅՈɅ]{2}).){2}(?!.*[ԅՈƪɅ]{2}))(?=((?![ʇɊƈѹ]{2}).)*(?=[Ɋƈʇѹ]{2}).(?!.*[ʇƈѹɊ]{2}))(?=(((?![նЏYI]{2}).)*(?=[IYնЏ]{2}).){2}(?!.*[նЏIY]{2}))(?=((?![ͼխɷȡ]{2}).)*(?=[ͼȡɷխ]{2}).(?!.*[ɷխȡͼ]{2}))(?=((?![ҝɞҎv]{2}).)*(?=[ɞҎvҝ]{2}).(?!.*[Ҏҝvɞ]{2}))(?=(((?![eƪGω]{2}).)*(?=[Geƪω]{2}).){3}(?!.*[ƪeGω]{2}))(?=(((?![ɂɿƱq]{2}).)*(?=[Ʊqɿɂ]{2}).){2}(?!.*[Ʊqɂɿ]{2}))(?=((?![ƣЖoɒ]{2}).)*(?=[Жɒoƣ]{2}).(?!.*[ƣoɒЖ]{2}))(?=(((?![Ҵԉձϻ]{2}).)*(?=[ձԉϻҴ]{2}).){2}(?!.*[ϻԉձҴ]{2}))(?=((?![ɆɟѧE]{2}).)*(?=[EѧɆɟ]{2}).(?!.*[ѧEɆɟ]{2}))(?=((?![ѪɝȾѸ]{2}).)*(?=[ѪѸɝȾ]{2}).(?!.*[ѪѸȾɝ]{2}))(?=(((?![ßΩԂɥ]{2}).)*(?=[ɥΩßԂ]{2}).){2}(?!.*[ɥßԂΩ]{2}))(?=(((?![ӃդƐϣ]{2}).)*(?=[ƐդӃϣ]{2}).){2}(?!.*[ϣդƐӃ]{2}))(?=(((?![ѪլѸԿ]{2}).)*(?=[ԿѪѸլ]{2}).){2}(?!.*[ԿѪլѸ]{2}))(?=((?![ɉшƻϙ]{2}).)*(?=[ɉƻшϙ]{2}).(?!.*[ϙƻɉш]{2}))(?=((?![ѹփʯΨ]{2}).)*(?=[ʯփΨѹ]{2}).(?!.*[ѹʯփΨ]{2}))(?=((?![ƕϯʮҏ]{2}).)*(?=[ƕҏʮϯ]{2}).(?!.*[ҏϯʮƕ]{2}))(?=((?![ՌȿSբ]{2}).)*(?=[բՌSȿ]{2}).(?!.*[SȿբՌ]{2}))(?=(((?![ИщɌK]{2}).)*(?=[ɌщИK]{2}).){2}(?!.*[ɌИщK]{2}))(?=(((?![aҵɸւ]{2}).)*(?=[ւҵaɸ]{2}).){2}(?!.*[aւɸҵ]{2}))(?=(((?![լѸխɷ]{2}).)*(?=[ɷѸլխ]{2}).){2}(?!.*[խɷլѸ]{2}))(?=(((?![ՉLʝϥ]{2}).)*(?=[LϥʝՉ]{2}).){2}(?!.*[ՉϥʝL]{2}))(?=((?![ʬϬȝɣ]{2}).)*(?=[Ϭɣȝʬ]{2}).(?!.*[ȝɣϬʬ]{2}))(?=(((?![ɺȴҵւ]{2}).)*(?=[ȴɺҵւ]{2}).){3}(?!.*[ҵȴɺւ]{2}))(?=(((?![ΞʇɊζ]{2}).)*(?=[ζɊʇΞ]{2}).){2}(?!.*[ΞɊζʇ]{2}))(?=(((?![դփӃΨ]{2}).)*(?=[ΨփդӃ]{2}).){2}(?!.*[ΨփդӃ]{2}))(?=((?![ԳuҦc]{2}).)*(?=[uԳҦc]{2}).(?!.*[ҦucԳ]{2}))(?=(((?![ԻЭɌщ]{2}).)*(?=[ԻɌщЭ]{2}).){2}(?!.*[ɌщԻЭ]{2}))(?=((?![ЉջѮӺ]{2}).)*(?=[ӺЉѮջ]{2}).(?!.*[ѮӺЉջ]{2}))(?=(((?![ӿѤɹN]{2}).)*(?=[ӿɹѤN]{2}).){3}(?!.*[ѤNɹӿ]{2}))(?=(((?![ƕʮBg]{2}).)*(?=[Bʮgƕ]{2}).){3}(?!.*[Bʮgƕ]{2}))(?=((?![կƛȸԓ]{2}).)*(?=[ƛȸԓկ]{2}).(?!.*[կԓƛȸ]{2}))(?=(((?![ɥДȸh]{2}).)*(?=[ɥhДȸ]{2}).){2}(?!.*[ɥhȸД]{2}))(?=(((?![ʁԺեW]{2}).)*(?=[եWԺʁ]{2}).){2}(?!.*[ԺʁWե]{2}))(?=((?![ɮςϿʢ]{2}).)*(?=[ʢϿɮς]{2}).(?!.*[ɮςʢϿ]{2}))(?=(((?![ձУAƾ]{2}).)*(?=[ƾУձA]{2}).){2}(?!.*[УAձƾ]{2}))(?=(((?![ԻϠɌʄ]{2}).)*(?=[ʄɌԻϠ]{2}).){2}(?!.*[ϠɌʄԻ]{2}))(?=((?![ɜҥմȶ]{2}).)*(?=[ҥȶɜմ]{2}).(?!.*[ҥȶɜմ]{2}))(?=(((?![ƏՀթϞ]{2}).)*(?=[թՀƏϞ]{2}).){2}(?!.*[ƏՀթϞ]{2}))(?=((?![ҩɃȽϛ]{2}).)*(?=[ɃȽϛҩ]{2}).(?!.*[ҩϛɃȽ]{2}))(?=((?![ҠȺԃD]{2}).)*(?=[ȺҠԃD]{2}).(?!.*[DԃҠȺ]{2}))(?=((?![ɆʊLϥ]{2}).)*(?=[LϥʊɆ]{2}).(?!.*[ʊϥɆL]{2}))(?=(((?![ͽѩɒЖ]{2}).)*(?=[ͽɒѩЖ]{2}).){2}(?!.*[ѩɒЖͽ]{2}))(?=(((?![ςϪʢƩ]{2}).)*(?=[ƩʢςϪ]{2}).){3}(?!.*[ςƩϪʢ]{2}))(?=(((?![ҁϥѧɆ]{2}).)*(?=[ϥѧҁɆ]{2}).){2}(?!.*[ѧҁϥɆ]{2}))(?=((?![Жϗѩʓ]{2}).)*(?=[ʓϗЖѩ]{2}).(?!.*[ʓЖϗѩ]{2}))(?=(((?![ʁեɋþ]{2}).)*(?=[ʁɋեþ]{2}).){2}(?!.*[þեʁɋ]{2}))(?=((?![Mnƻɉ]{2}).)*(?=[Mɉƻn]{2}).(?!.*[ƻMnɉ]{2}))(?=(((?![HʬϬѺ]{2}).)*(?=[HѺʬϬ]{2}).){2}(?!.*[ϬѺʬH]{2}))(?=(((?![cիըҦ]{2}).)*(?=[ըҦիc]{2}).){2}(?!.*[cիҦը]{2}))(?=((?![ȸɥկΩ]{2}).)*(?=[ɥΩկȸ]{2}).(?!.*[ɥȸկΩ]{2}))(?=(((?![ʫҝԲɞ]{2}).)*(?=[ʫԲɞҝ]{2}).){2}(?!.*[ʫɞԲҝ]{2}))(?=(((?![ҺЋϗѩ]{2}).)*(?=[ѩҺϗЋ]{2}).){3}(?!.*[ҺѩЋϗ]{2}))(?=((?![ʯΨɎч]{2}).)*(?=[ʯΨɎч]{2}).(?!.*[ʯΨɎч]{2}))(?=(((?![ѮɔЉA]{2}).)*(?=[ЉɔѮA]{2}).){2}(?!.*[ѮɔAЉ]{2}))(?=(((?![ʞӶdN]{2}).)*(?=[dNʞӶ]{2}).){2}(?!.*[ӶNdʞ]{2}))(?=(((?![ԀŋҔɴ]{2}).)*(?=[ŋԀҔɴ]{2}).){3}(?!.*[ҔɴŋԀ]{2}))(?=(((?![ΠЪƏթ]{2}).)*(?=[ƏΠթЪ]{2}).){3}(?!.*[ΠթЪƏ]{2}))(?=(((?![OՌѿբ]{2}).)*(?=[ՌOբѿ]{2}).){2}(?!.*[OբՌѿ]{2}))(?=((?![ɮȾʢѪ]{2}).)*(?=[ɮȾʢѪ]{2}).(?!.*[ѪȾɮʢ]{2}))(?=((?![ЪϤՋΠ]{2}).)*(?=[ϤΠЪՋ]{2}).(?!.*[ՋΠЪϤ]{2}))(?=((?![Մͽӻϼ]{2}).)*(?=[ͽϼՄӻ]{2}).(?!.*[ϼͽՄӻ]{2}))(?=((?![ԋҳѦЩ]{2}).)*(?=[ѦԋЩҳ]{2}).(?!.*[ѦЩҳԋ]{2}))(?=((?![gҶҸB]{2}).)*(?=[BҶgҸ]{2}).(?!.*[ҸBgҶ]{2}))(?=(((?![ɢλҡѥ]{2}).)*(?=[λҡɢѥ]{2}).){2}(?!.*[ѥλɢҡ]{2}))(?=(((?![AϻЉձ]{2}).)*(?=[ϻձЉA]{2}).){2}(?!.*[ϻձЉA]{2}))(?=((?![tRիp]{2}).)*(?=[Rtpի]{2}).(?!.*[tpRի]{2}))(?=(((?![ɮȹϿÞ]{2}).)*(?=[ϿɮÞȹ]{2}).){2}(?!.*[ϿɮȹÞ]{2}))(?=((?![ϯժʮџ]{2}).)*(?=[ժџϯʮ]{2}).(?!.*[џϯʮժ]{2}))(?=(((?![HʬȠҨ]{2}).)*(?=[HҨȠʬ]{2}).){2}(?!.*[ȠҨʬH]{2}))(?=((?![ՒԉPϻ]{2}).)*(?=[ԉϻPՒ]{2}).(?!.*[PϻԉՒ]{2}))((?=Գ[նƎuc]|ƕ[Bʮȴҏ]|ϣ[ԏɂӃƐ]|Ʊ[ɿϬӄɂ]|Ѿ[ϭϢҸҥ]|ͽ[ѩӻՄɒ]|ɷ[խͼլ]|փ[դiѹΨ]|ϛ[ɅɃȽՀ]|Ԃ[ɥѭմß]|խ[ȡɐѸɷ]|P[ȠՒԉ]|ӷ[ЩEՊƆ]|Ə[ΠթƣϞ]|ч[xɎΨ]|ʄ[ԈϠԻҺ]|Љ[AѮϻջ]|ɒ[ʈƣЖͽ]|ʞ[ӶɔNЦ]|Ɛ[ϣɰqդ]|ʮ[ϯժƕg]|ɥ[ȸДԂΩ]|Ҕ[ŋՐɺɴ]|χ[Ԏѯ]|Ջ[ΠϤԾտ]|Ɏ[чʯֆ]|ҥ[մѬѾȶ]|ɞ[ҝҎԲ]|ҏ[ƕՐϯɺ]|Հ[ϛթϞw]|y[ϼԈҝՎ]|λ[ѥՎϼҡ]|Մ[ͽҡϼʈ]|ϟ[ϫϤԾ]|Ћ[ǷϠҺϗ]|ʫ[ԲԈҝԻ]|ǝ[gjɰժ]|Ԅ[ҡҹʟʈ]|ʌ[kՌэC]|ȶ[ҥЊɜʟ]|Ɍ[щИԻϠ]|ի[Rtըc]|Ո[ƪƺЪɅ]|ƺ[ՈϤϫω]|ß[ԂΩɜҤ]|I[նЏљ]|ҷ[ȡэCɐ]|Ц[ςbʞɹ]|Ǝ[ǂȺԳG]|ӄ[ƱӾѺ]|ʇ[ζiɊѹ]|ֆ[ɎF]|ɏ[ѠΞƋ]|Բ[ɞʫЭ]|Ի[ɌЭʫʄ]|ƪ[ԅωGՈ]|ȡ[խɋͼҷ]|Ϡ[ɌдʄЋ]|ɋ[эʁþȡ]|U[ɝɄՅʝ]|ɺ[ҵȴҏҔ]|Ƚ[ԅϛDҩ]|Ɋ[ƈʇΞ]|ժ[Φʮǝџ]|Ӿ[ӄɂԏ]|Ψ[Ӄчʯփ]|Ω[Ղկßɥ]|щ[KɌЭ]|ɉ[nҶшƻ]|Ժ[WԱե]|G[ƎeҠƪ]|ղ[կՂՑɃ]|Ӷ[ԷʞdѮ]|u[ȺԳQҦ]|Ѡ[ɴɏՐ]|ƛ[ԓՑѿկ]|ɜ[ɀմßȶ]|Ҵ[ԉձʡɧ]|ȿ[kSՌԃ]|ɂ[qӾϣƱ]|Պ[ӷɧƸʡ]|Щ[ѧѦӷԋ]|Ⱦ[ѪɝʢՅ]|Ƀ[ղҩwϛ]|Ҏ[vҜɞ]|ɐ[ҷɄɝխ]|ԏ[ϣxӾ]|Ҁ[ҹϞҤw]|մ[ԂҥɜϢ]|ҳ[ДԋϙѦ]|Ϛ[jɰqԼ]|w[ҀՀɃՂ]|E[ӷɟѧʡ]|У[μAbƾ]|ձ[ҴϻƾA]|ɟ[ɆμEƾ]|Ҥ[ҀßՂɀ]|v[ȵҎՎҝ]|ш[ϢϙɉҸ]|Ͽ[ɹɮςÞ]|O[fCՌѿ]|ʁ[ԶեWɋ]|ȹ[ÞԿɮ]|Ϟ[ՀէҀƏ]|ԋ[ƻҳЩƆ]|ƅ[fԓՉѿ]|ω[ƺeճƪ]|ʈ[ɒԄՄէ]|Ԉ[ʫʄӻy]|Ƌ[ζՐϯɏ]|ɰ[ǝƐΦϚ]|ȴ[ƕϭւɺ]|Δ[Չhҁԓ]|Π[ՋЪoƏ]|Ϫ[ʢƩʊՅ]|ӻ[ҺԈͽϼ]|ʝ[ՉLfU]|Ծ[ϟrՋ]|þ[ɋեͼ]|ӿ[ѤɹÞ]|բ[ՌՑSѿ]|ҡ[λՄɢԄ]|ɸ[ȻՃaҵ]|д[ϠИǷ]|ճ[ωϫл]|ɀ[ҹҤʟɜ]|л[ճeљ]|Ϥ[ϟЪƺՋ]|c[ԳYҦի]|Ռ[Oʌբȿ]|ն[ԳǂYI]|Ʌ[ԅϛՈթ]|ҝ[yɞʫv]|p[ƜRt]|ƣ[էƏɒo]|Ҷ[Ҹɉgj]|A[УձɔЉ]|Þ[ȹϿӿ]|Ƿ[дЋԒ]|k[QԶȿʌ]|ջ[ՒӺЉ]|Ɇ[ʊѧϥɟ]|ʢ[ςϪɮȾ]|ѭ[ДϢϙԂ]|ʘ[ЏƜt]|ѹ[ʇʯփƈ]|ʟ[Ԅȶɀɢ]|ϯ[ҏƋʮџ]|լ[ԿɷѸ]|Ƹ[ՊʙƆȝ]|N[ɹʞdѤ]|ς[ЦϿʢƩ]|ǂ[eƎљն]|ѧ[ɆEҁЩ]|ɴ[ѠҔԀ]|Ʉ[ɐfCU]|ҹ[ԄҀէɀ]|Ւ[ջPϻ]|ѥ[ɢλaՃ]|o[ΠտЖƣ]|g[BҶʮǝ]|Կ[լѪȹ]|Џ[ʘIY]|Y[ctЏն]|Ҡ[ȺDGԅ]|Ѧ[Щҁҳh]|Ѻ[HϬӄ]|ɹ[NЦϿӿ]|ԓ[ƛƅΔȸ]|f[OƅɄʝ]|L[ʝʊՅϥ]|ϼ[yӻλՄ]|џ[ζժiϯ]|ҩ[SɃȽՑ]|Ʃ[Ϫμbς]|դ[փƐӃΦ]|Ѯ[ӶӺЉɔ]|ƻ[ɉԋϙM]|ѩ[ҺϗͽЖ]|ʊ[μɆϪL]|Ж[ɒʓѩo]|B[ƕҸgϭ]|ԅ[ҠɅƪȽ]|ɔ[ʞѮAb]|ϗ[ЋʓԒѩ]|Ɔ[ӷMƸԋ]|љ[лǂI]|ȸ[ɥԓhկ]|q[ƐɿϚɂ]|Ҹ[шҶBѾ]|ʡ[ҴƾEՊ]|Ԏ[dχԷ]|j[ϚnǝҶ]|Ҧ[uըcϧ]|ϻ[ՒЉԉձ]|ʙ[ƸԼɣM]|ե[ʁþԺ]|Ƞ[PHҨ]|Φ[ɰդiժ]|Њ[ɢaѬȶ]|b[ɔƩЦУ]|Չ[ʝƅϥΔ]|ϧ[ԶҦWQ]|Ճ[ѥɸȵՎ]|Ҩ[ɧԉȠʬ]|ҁ[ΔѧѦϥ]|Ց[ҩƛղբ]|ɿ[qԼɣƱ]|μ[УƩɟʊ]|e[ωǂGл]|Һ[Ћʄѩӻ]|ѯ[dѤχ]|Ԓ[Ƿюϗ]|ҵ[ɸɺŋւ]|տ[Ջʓro]|ϙ[ѭƻҳш]|R[իԱp]|Ɯ[pʘ]|r[Ծюտ]|ƈ[ɊѹF]|M[ʙnƆƻ]|i[փʇΦџ]|ƾ[ձУʡɟ]|ɝ[ѸȾɐU]|ю[Ԓʓr]|Д[hҳѭɥ]|a[Њѥւɸ]|Յ[LUϪȾ]|ϭ[ѬBѾȴ]|Ѹ[Ѫɝխլ]|D[ԃȽҠS]|Ⱥ[ԃuƎҠ]|Ȼ[ŋȵɤɸ]|э[ʌԶҷɋ]|Ѥ[ѯӿN]|ԃ[ȺDȿQ]|ȵ[ҜȻՃv]|S[բȿҩD]|Ղ[ҤwΩղ]|ɢ[ѥҡʟЊ]|ɣ[Ϭɿȝʙ]|Վ[yvλՃ]|Ϭ[ɣʬƱѺ]|Ӄ[ϣxΨդ]|թ[ƏɅЪՀ]|ȝ[ʬƸɧɣ]|Ԁ[ɤɴŋ]|ѿ[ƅOƛբ]|H[ȠʬѺ]|F[ֆƈʯ]|Ѫ[ѸȾɮԿ]|է[ʈƣϞҹ]|ʯ[ѹFɎΨ]|ŋ[ȻҔԀҵ]|ɤ[ԀҜȻ]|ԉ[ҴPҨϻ]|ͼ[ȡɷþ]|t[իʘpY]|Ϣ[ѭմѾш]|Э[щԲԻ]|ɮ[ʢѪϿȹ]|ϫ[ƺճϟ]|Ѭ[Њւϭҥ]|Լ[Ϛnɿʙ]|Ξ[ζɊɏ]|Է[ԎӺӶ]|Q[ϧkԃu]|ւ[ҵaѬȴ]|Ր[ѠҏҔƋ]|ը[իԱWҦ]|ʓ[տϗюЖ]|K[щИ]|Ӻ[ԷѮջ]|x[чӃԏ]|И[KɌд]|ʬ[HҨȝϬ]|Ա[RըԺ]|ɧ[ȝҴՊҨ]|n[jɉMԼ]|C[ʌҷɄO]|W[ϧըʁԺ]|h[ДѦΔȸ]|ϥ[ՉLɆҁ]|Ъ[ΠՈϤթ]|կ[Ωղƛȸ]|ζ[џΞʇƋ]|Ҝ[ɤҎȵ]|Զ[ϧkʁэ]|d[ԎNѯӶ]).){3,}\3

Test here: http://regex101.com/r/kF2oQ3/1
(crickets chirping)
No takers? It's oddly disappointing to think of posting the spoiler with no evidence that anyone looked at it long enough to understand what type of problem it is.
I'm writing a complete explanation to post later but I think I'd be happier if someone beat me.
When I said it was not "computationally difficult"... it is an instance of an NP-complete problem, but not a big instance.
Hint: it's a type of pencil-and-paper puzzle. But I'd be quite impressed if you can solve this one with pencil and paper alone (after decoding the regexp into a form suitable for printing).
Spoiler time
There are multiple levels of spoilers here. If you didn't solve the regexp yet, you might want to try again after reading just the first spoiler block. The actual key that matches the regexp is after the last spoiler block.

This regexp encodes a Slitherlink puzzle.

Once you figure out what's going on and convert the regexp into a Slitherlink grid, you'll quickly discover that it's harder than the average Slitherlink. It's on a 16x16 square grid, larger than the usual 10x10. It is also slightly unusual in having no 0 clues and a relative shortage of 3's. 0's and 3's are the easiest clues to work with, so I didn't want to give you a lot of them.

Second layer of spoilage:

When you're solving the Slitherlink puzzle, an extra surprise kicks in: this Slitherlink has more than one solution. If you're a regular Slitherlink solver, and you have a habit of making deductions based on the assumption of a unique solution, you might have been confused by that. If so, you're a cheater and this is your punishment! Part of the job of a puzzle solver is to find out how many solutions there are.

Final layer of spoilage:

The final twist: the 2 solutions to the Slitherlink are mostly identical, but one is slightly longer than the other. You need to find the short one. If you only found the long one and encoded it as a string to match the regexp, the string would be 257 characters long. The path goes through 256 nodes, but you have to repeat the first node at the end to close the loop. And if you got that far, you might have thought I made a mistake and forgot to count that extra character. Nope! and/or Gotcha! (and/or Boosh! and/or Kakow!)

The short solution is 254 segments long and encodes to a string of 255 characters which is the key. Since you can start at any node on the loop and proceed clockwise or counterclockwise, there are 254*2=508 possible answers.

Non-match: bananabananabanana
Match: ƜpRԱԺեþɋэʌkȿՌOfɄCҷɐխɷլԿѪɮȹÞӿѤNɹЦʞӶdѯχԎԷӺջՒϻЉAɔbУƾձҴԉҨʬHѺӄӾԏxчɎֆFƈɊΞζџiփΨӃϣɂƱϬɣɿqϚɰƐդΦժʮgBƕȴւҵɺҏϯƋՐѠɴҔŋԀɤȻɸaЊѬҥѾҸшɉҶjnMʙƸՊʡEɟμƩςʢϪʊLՅȾɝUʝՉϥҁѧЩӷƆԋҳϙѭϢմԂɥȸhΔԓƛѿբՑҩSDȽԅҠGeωƪՈɅϛɃwҀҤՂΩßɜȶʟɀҹԄҡλѥՃȵҜҎɞԲЭщɌИдϠʄԻʫҝyϼӻҺЋϗѩͽɒʈէϞՀթЪΠƏƣoտʓюrԾϟϤƺϫճлљIնǂƎԳuȺԃQϧԶʁWըիcYЏʘƜ
Proof: http://regex101.com/r/pJ3uM9/2

Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked.

I tried but didn't find it is planar...

Perl flavour, 158 [cracked]
Here's my first attempt:
(?(R)|^(?=[a-z]))((?!.*(?&K))(((?|([?-K])|(?'K'$)|(?'k'j'k'?)|(?'k'C[^_^]{3,33}))(?(3)\3|3)){3}(?(R)R(-.-)|(?R))(?'k'<grc>-(?!(?&k))\4(?(R)|\$\4(?5)$)))|(?R))

Test it on ideone.com

 (?(R)|^(?=[a-z])) the very first character must be a lowercase letter
(?!.*(?&K)) the string cannot contain letters in the ASCII range [?-K]
(?|...|(?'k'j'k'?)|...) matches j'k (the other groups are essentially red herrings)
(?(3)\3|3){3} recursively match the 3rd group, or '3' after 3 levels of recursion, repeated 3 times
(?(R)...|(?R)) recurse over the entire regex once or match a few characters
...(?!(?&k))... I think this is [?-K] again, but I can't remember
(?(R)|...$) after recursion, match some groups and end the string
|(?R) if anything fails to match, then it's time for infinite recursion :D

Match: j'k3j'kj'k3j'kj'kj'k3j'k3j'kj'k3j'kj'kj'k3R-k-<grc>-j'k<grc>-j'k$j'k-k- Non-match: HOLYCRAPTHATWASEVIL (match available at http://ideone.com/pXaGaX for proof)

Everybody who tried to solve this and got even halfway there is now prepared to send 2 bug reports and 3 documentation patches for the perl regexp engine. (And all of us for different things)

+1 for cool key and having emoticon in your regex [^_^] (-.-)

@WumpusQ.Wumbley Well done! I think the robbers are winning this one :(

My previous comment was mostly a joke, but maybe some explanation would be nice. The use of named capture groups inside (?|...) is tricky, but it is documented. See the passage in perlre that starts with Be careful when using the branch reset pattern in combination with named captures. The trick is that groups that have the same number but different names are the same group, while groups that have the same name but different numbers are different groups.

@WumpusQ.Wumbley There's no explanation because I hardly understand it myself. If I get the time tomorrow I will add a few comments though.

When I built my answer I was surprised that the 4th branch with the C[^_^]{3,33} never came into play. I didn't know if it was an intentional red herring or a mistake.

@WumpusQ.Wumbley Yeah that was a last-minute red herring. I've added some brief comments to my answer.

JS flavor, 9998 bytes [cracked]
^(?!.*(.).*\1)(?=M)((?=!7|!D|!a|!§|!¾|!Ö|!ù|!Ě|!į|!Ň|"C|"s|"t|"¡|"°|"»|"è|"ñ|"÷|"ķ|"ļ|"Œ|#W|#k|#l|#o|#q|#¶|#À|#Â|#Æ|#č|%!|%1|%O|%ÿ|%Ĕ|%Ğ|%Ī|%ĭ|&e|&q|&Õ|&æ|&ü|&đ|&Ĩ|'%|'`|'k|'¯|'É|'í|'þ|'ė|'Ğ|'ĩ|'Ĳ|'ļ|'ł|,%|,'|,l|,ª|,®|,¸|,¹|,ã|,õ|,Ċ|,Ġ|,Ī|,İ|,Ņ|-U|-V|-»|-Ï|-Þ|-ì|0_|0u|0°|0Ġ|0İ|0ł|1#|1-|1g|1å|1é|1ą|1Ļ|1ń|2B|2O|2¬|2ë|2ò|2õ|2Ğ|2ĩ|2į|2Ĳ|2ļ|3d|3²|3Ï|3Þ|3ß|3ç|3ø|3ĉ|3ķ|3ĸ|3Ŀ|4c|4£|4ß|4ã|4Ċ|4ģ|4Ĩ|4ő|4Œ|5&|5Q|5û|5Ā|5ě|5ĩ|6ú|6Ķ|6Ł|7Q|7V|7e|7²|7Á|7Þ|7à|7đ|7Ġ|7ĵ|8w|8¯|8¾|8ņ|8ő|9H|9Y|9i|:6|:s|:¬|:ð|:ü|:Ĉ|:Ċ|:Ĵ|:ĸ|:Ŀ|;X|;®|;¯|;²|;¸|;Ó|;à|;ĥ|;Œ|<-|<t|<å|<ø|<Į|<Ľ|<ō|=&|=l|=¨|=Á|=Ý|=Č|=Ĩ|=Ń|>-|>±|>¸|>Ä|>à|>ð|>ó|>Ī|@B|@F|@_|@³|@´|@Ó|@Ü|@ã|@û|@Ğ|@ğ|@Ĭ|@İ|@Ŀ|A5|AV|A_|Ax|A¹|AÅ|AĞ|AĶ|Aņ|Aō|B¼|BÂ|Bä|Bç|BĊ|Bį|Bİ|BĻ|BŅ|C1|C<|CG|Cy|C~|C¼|Cì|Cù|Cō|DT|DU|Dc|Dj|D¤|DÂ|DÑ|DĀ|Dİ|E,|E¬|E¼|E×|Eā|Eė|Eń|FZ|Ft|F»|F¿|FÈ|FØ|Fç|Fì|Fć|FĬ|Fı|FŅ|Gj|Gl|Gv|G¯|Gâ|Gï|GĖ|Gę|GĦ|Gĭ|H8|HB|HS|Hu|H¥|HÃ|HÌ|Hø|HĆ|HĒ|HĬ|Hĭ|I=|It|I©|Iæ|IĿ|Iō|J1|J3|J5|JQ|JÉ|JÔ|J×|Jă|JĲ|K-|KP|KÄ|Kî|Kā|KĐ|Kġ|KĨ|KĴ|L!|LÐ|Lá|LĚ|LĠ|M5|M¿|MÅ|Må|MĈ|MŊ|N,|N2|N5|NB|Nh|NÂ|NØ|NÜ|NĖ|Nĝ|NŃ|O;|Of|O¯|O¸|Oå|OĈ|Oď|Oē|OĲ|P7|PQ|Pp|P£|Pđ|PĴ|Pŀ|Q7|QR|Q¥|QÝ|Qî|Qī|Qĸ|Qŀ|Qő|R0|RA|RI|RN|R¥|R¼|Rö|Rû|RĬ|RĮ|RŎ|S;|SC|ST|Sd|Sy|S§|TX|Td|Tw|Tª|T¿|Tõ|U0|U:|UÊ|Uĉ|Uę|UĢ|UĦ|Uį|UĶ|Uň|V:|Vq|Vs|V¦|VÂ|Vó|Vþ|Wh|WÅ|WÉ|Wê|Wô|Wģ|Wň|X:|XI|XS|X`|Xâ|Xċ|Xė|XĠ|Xģ|Y"|YX|Yb|Yn|Yo|Y£|Y§|YÌ|YÎ|YÚ|Yá|Yă|YĜ|Yĥ|YĿ|Yŉ|Z6|Z:|Z;|Z¶|Zå|Zæ|Zċ|Zĺ|ZŊ|_,|_-|_c|_g|_à|_ĉ|_Ħ|_ł|`I|`z|`ð|`ă|`Ĳ|`ĳ|a4|a9|aF|a½|aä|añ|aď|aĝ|aĸ|b&|b7|b¸|bÝ|bë|bĺ|bņ|bŊ|c&|cP|cr|cÄ|cÑ|cÖ|cČ|cę|cĩ|cĲ|cķ|cĿ|d"|dI|d¥|d¦|dä|dģ|eK|e²|eý|eą|eČ|eĔ|eĲ|eĶ|eń|fM|fm|f¥|fÇ|fÒ|fæ|fì|fć|fě|fĝ|g!|gN|gx|gz|gÍ|gĚ|gĞ|h"|h¬|h¶|hä|hì|hï|hĆ|hņ|hŋ|hŏ|i'|i9|i¢|i¤|iÓ|iÖ|iā|iĕ|iĝ|iį|iĶ|jH|jT|j£|jµ|j·|jø|jĸ|jŐ|k0|k2|kA|k~|k¨|k½|kÙ|l&|lX|lc|ln|l£|l¥|lµ|lÃ|lå|lé|lĩ|lŌ|lŒ|m-|mW|mÐ|mĘ|mĮ|mĸ|n!|n2|nJ|nU|n¬|n½|nĆ|nĒ|nĔ|nĭ|nŇ|o5|o<|oD|oM|oÖ|oĂ|ps|pz|pº|pê|pĢ|pĥ|pĲ|qK|qa|q§|qÛ|qç|qý|qă|qĒ|qĴ|qĶ|qń|rA|re|rj|r§|r«|r¿|rÃ|rß|rò|rĔ|rĖ|rĢ|rķ|sD|sc|sÍ|sĀ|tT|tW|ta|t£|t¯|t±|tÊ|tÑ|tĚ|tļ|uV|ua|ub|uf|u¦|u´|u»|u¾|uË|uØ|uĞ|uĪ|uĹ|v:|vi|vw|v§|v½|vÄ|vÈ|vÌ|vù|vĮ|vļ|vŉ|vŎ|w!|w0|wZ|wg|wÞ|wæ|wò|wù|wĥ|wħ|wŎ|xD|x©|x®|xá|xû|xģ|xľ|xł|yC|ya|yr|y²|yÉ|yò|yĆ|yĠ|yĵ|yŒ|zM|zi|z¯|zø|zú|zć|zđ|~5|~Y|~¨|~º|~Û|~å|~ê|~ô|~ü|~ą|~ĥ|~Ī|~İ|~Ľ|~ō|¡J|¡±|¡¼|¡Ê|¡Ë|¡Ñ|¡ã|¡Ă|¡Ġ|¡Ĩ|¡ī|¡Œ|¢@|¢G|¢±|¢º|¢ç|¢Đ|¢İ|¢Ŀ|£F|£e|£Þ|£ä|£Ĵ|¤P|¤p|¤¯|¤µ|¤þ|¤ď|¤Ģ|¤ī|¥Z|¥¤|¥È|¥Ñ|¥û|¥Ď|¦T|¦Y|¦Z|¦a|¦b|¦e|¦q|¦r|¦¡|¦³|¦ĩ|¦Ĳ|¦ĺ|§b|§n|§w|§¿|§Ç|§Đ|¨3|¨Ã|¨Ë|¨Î|¨ë|¨÷|¨Č|¨ġ|¨Ī|¨Ĺ|¨ł|¨Œ|©I|©Z|©Ý|©ë|©ü|©ġ|©ŋ|ªP|ªo|ªr|ª¨|ª¯|ª²|ª¾|ªÇ|ªÔ|ªÙ|ªĉ|«K|«p|«£|«¨|«©|«¬|«®|«Õ|«Þ|«ß|«ö|«Đ|¬!|¬j|¬ª|¬¼|¬À|¬Ã|¬Ì|¬ú|¬ő|®#|®´|®É|®č|®đ|®ī|®ŉ|¯9|¯g|¯n|¯¹|¯È|¯Ē|¯ę|¯ġ|°N|°d|°k|°m|°s|°²|°È|°Î|°ê|°ó|°ŉ|±%|±R|±Y|±r|±æ|±Ŀ|±ń|²D|²H|²U|²×|²ã|²ä|²ç|²ą|²ħ|³`|³Ë|³ã|³ë|³ò|³ô|³ø|³Ċ|³Ĥ|³Ŀ|´~|´§|´Ê|´è|´Ķ|´Ŏ|µ:|µC|µ¢|µØ|µó|µĠ|µģ|µĤ|¶!|¶0|¶7|¶Y|¶¤|¶À|¶Ö|¶Ħ|¶ő|·p|·Á|·Ç|·ë|·î|·Ļ|·Ŋ|¸X|¸Z|¸¦|¸÷|¸ú|¸Đ|¸ĝ|¹,|¹>|¹M|¹Z|¹a|¹¢|¹Ì|¹×|¹Ø|¹þ|¹ĉ|¹Ĩ|º>|ºj|ºá|ºç|ºý|ºć|»2|»c|»°|»Ä|»ñ|»Ġ|»Ŋ|¼3|¼F|¼c|¼d|¼x|¼y|¼Ä|¼É|¼û|¼Č|¼ē|¼Ĩ|¼Ĭ|¼Ĵ|¼Ĺ|½k|½Ø|½ø|½ħ|¾2|¾:|¾L|¾¿|¾Á|¾ñ|¾ô|¾÷|¾đ|¾ĥ|¾Ń|¿D|¿«|¿ö|¿ø|¿Ĕ|¿ę|¿Ļ|¿ō|À3|ÀW|À°|ÀÆ|Àđ|ÀĘ|ÀĞ|Àģ|Àİ|Á§|Áé|Áõ|ÁĜ|Áĝ|ÁĪ|Áŉ|Â&|ÂB|ÂM|Â¿|Âø|Âħ|Âĺ|ÂĻ|ÂŁ|Âŉ|Ã`|Ãt|Ã¢|Ã©|ÃĆ|ÃĖ|Ãĥ|Ãĩ|Ä_|Ä¥|ÄÌ|ÄÞ|Äð|ÄĆ|Äİ|ÄŁ|Å@|ÅY|Å«|ÅĄ|Åı|Åĸ|Æ;|ÆK|Æv|Æµ|Æ¹|Æ½|ÆÇ|ÆÛ|Æõ|Æü|ÆĆ|ÆĤ|Çd|Çº|ÇĔ|Çě|Çģ|ÇĶ|ÇĽ|Èd|Èz|È~|È´|È½|ÈÂ|Èæ|Èõ|ÈŅ|ÉH|ÉO|ÉÌ|Éï|ÉČ|Éę|ÉĬ|Éĭ|ÉĴ|ÉŎ|Ê%|Ê6|ÊI|Êk|Êy|Ê³|ÊÁ|Êñ|Êą|ÊŃ|Ë!|ËH|Ëh|Ëº|Ë»|ËÆ|Ëğ|ËŌ|Ì3|Ì7|ÌG|Ìp|Ì«|Ìè|Ìï|ÌĮ|ÌŎ|ÍZ|Íd|Í©|ÍÖ|Íá|Íê|Íø|Íā|ÍŊ|Î-|Î_|ÎÊ|Îæ|Îó|Îù|ÎĀ|ÎĐ|Îġ|Îĭ|ÎŇ|Ï"|Ï5|Ï7|ÏA|ÏH|Ïl|Ï±|Ï¹|ÏÈ|ÏØ|ÏÚ|ÏÛ|ÏĻ|Ïŉ|ÐR|Ð·|ÐÀ|ÐÓ|ÐĒ|Ðě|ÐĶ|Ðľ|Ñ©|Ñµ|ÑÅ|ÑÈ|Ñŉ|ÒV|ÒÇ|Òĉ|Òħ|ÒŃ|Ó2|ÓD|ÓÎ|Óç|Ó÷|Óù|ÓĈ|Óķ|ÔE|ÔJ|Ôf|Ôy|ÔÆ|ÔÞ|Ôâ|ÔĂ|ÔĨ|Õ3|ÕG|Õh|Õ¹|ÕÁ|ÕÐ|Õÿ|Õğ|Õī|Ö7|ÖB|Öª|Ö¼|Öÿ|Öħ|Öĳ|×6|×>|×f|×¢|×µ|×·|×Â|×Ê|×Ñ|×ã|ØG|Ø¯|ØÄ|ØÊ|Øé|Øë|ØĊ|ØŇ|ØŐ|Øő|Ù:|Ùh|Ùx|Ù²|Ùč|Ùē|Ùę|Ùě|ÙĨ|ÙŇ|ÚE|Úq|Ú®|ÚÄ|ÚÒ|ÚÜ|Úä|Úí|Úı|Úķ|Û'|ÛW|Ûo|Ût|ÛÓ|Ûô|Ûõ|Ûû|Ûŉ|Ûŋ|Ü!|ÜJ|ÜÆ|ÜŐ|ÝR|Ýg|Ýq|Ýu|ÝÜ|Ýß|Ýð|Ýø|Ýč|ÝĶ|Ýŉ|Þº|ÞÝ|ÞĂ|Þą|Þć|ÞĠ|ÞĨ|ßu|ßÀ|ßė|à4|àS|à`|àk|à§|àé|àø|àĊ|àę|àģ|àĬ|á3|á£|á¶|áÄ|áÏ|áÑ|áâ|áü|áČ|áĽ|áņ|áŌ|â#|âY|â£|âº|âÓ|âġ|âĭ|âı|âŐ|âŒ|ã,|ã1|ã7|ã8|ãé|ãĭ|ä3|ä6|äN|ä¢|ä©|ä¬|äÏ|äĖ|äį|äŏ|åN|å¡|å¾|åØ|åë|åû|åč|åě|æ7|æT|æt|æ¸|æá|æï|æā|æĳ|ç2|çA|çJ|çl|ç¥|ç¬|çĝ|çĸ|èl|èq|èÓ|èÙ|èČ|èĖ|èĩ|èņ|èŉ|èő|éV|éZ|é®|é´|éí|éó|éû|éą|éě|éĭ|éŃ|ê5|êv|ê«|ê¶|êº|êÃ|êÔ|êİ|ëB|ëb|ë¤|ë¨|ëÎ|ëę|ëĞ|ì#|ì,|ì=|ì>|ìQ|ìS|ìV|ìº|ìā|ìġ|íJ|íV|í~|í¶|íò|íø|íă|íė|íĭ|î<|î=|îD|îR|îµ|îÚ|îÛ|îå|îê|îþ|îĒ|îĜ|îğ|ï%|ï,|ïa|ïu|ïÀ|ïÁ|ïá|ïĄ|ïą|ïċ|ïġ|ïĿ|ïŁ|ïŌ|ð6|ðE|ðp|ð¬|ðÞ|ðä|ðĚ|ðğ|ðļ|ñ1|ñ2|ñX|ñi|ñá|ñú|ñû|ñü|ñį|ñŊ|òB|ò«|ò¿|òÝ|òê|òď|ó5|óÄ|óÇ|óÈ|óÓ|óÕ|óĨ|óļ|ô4|ôh|ôÖ|ôî|ôþ|ôğ|ôŅ|õo|õ¢|õ¶|õÆ|õÓ|õä|õČ|õĕ|õģ|ö7|ö@|ön|ö¢|öÉ|öÒ|öÛ|öâ|öĝ|÷-|÷J|÷p|÷Ò|÷Ģ|÷ĭ|÷ı|÷ŉ|ø,|øo|ø¥|øÆ|øç|øè|øù|øĤ|øĥ|øħ|øň|ù7|ù9|ùs|ùu|ù¹|ùÍ|ùĆ|ùę|ùě|ùĹ|úG|úÅ|úÕ|úÖ|úÜ|úã|úç|úĂ|úĦ|û%|û;|ûR|ûh|ûu|ûz|û´|ûÐ|ûë|ûń|ûŊ|ü_|ü²|üê|üē|üğ|üł|üŅ|ý8|ý¨|ý©|ýÍ|ýÜ|ýĄ|ýċ|ýĩ|ýı|ýĲ|ýĸ|ýł|ýň|ýŎ|þ;|þD|þJ|þT|þr|þ·|þè|þĆ|ÿO|ÿÒ|ÿæ|ÿð|ÿć|ÿğ|ÿŇ|ĀA|ĀR|Ā_|Āv|Āá|ĀĘ|Āģ|Āİ|ā6|āM|ā¸|āä|āĮ|ĂX|ĂÁ|ĂÕ|ĂĚ|Ăķ|ĂĹ|ă"|ă°|ă¸|ăÉ|ăĆ|ăĚ|ăğ|ăĸ|ăĻ|ăŃ|ĄG|ĄJ|ĄK|Ą`|Ąc|Ąd|Ąg|Ąl|Ą³|ĄÄ|ĄÊ|ĄÌ|Ąú|ĄĽ|ą;|ąL|ąc|ąd|ąo|ąr|ą®|ą±|ąÄ|ąÅ|ąÇ|ąÍ|ą×|ąĈ|ąĎ|ąĐ|ąĩ|ąŌ|Ć´|Ć¸|Ć¼|ĆÑ|ĆØ|Ćí|ĆĊ|Ćņ|ĆŌ|ć4|ćx|ćy|ć¦|ć«|ćù|ćŃ|Ĉ&|Ĉ8|ĈE|ĈK|Ĉn|Ĉ¨|Ĉà|Ĉé|Ĉû|Ĉđ|Ĉĥ|ĈĪ|Ĉī|Ĉņ|ĉ@|ĉa|ĉÇ|ĉ×|ĉĩ|ĉň|Ċ#|Ċb|Ċt|Ċ»|ĊÁ|ĊÚ|Ċä|Ċÿ|Ċĝ|Ċĩ|Ċį|ċ'|ċD|ċ¶|ċÖ|ċê|ċþ|ċğ|ċņ|ČM|Čs|Č£|ČĨ|Čį|č±|čÖ|čè|čć|čğ|čń|čŉ|Ď`|Ď¡|Ď·|Ď¾|Ď¿|Ďą|Ďĳ|Ďŋ|ď"|ď5|ď8|ď=|ďD|ďs|ďØ|ďÚ|ďí|ďġ|ďĩ|ďļ|ĐF|ĐS|Đg|Đk|Đn|Đv|Đ~|ĐÖ|ĐÚ|ĐÜ|Đâ|ĐĞ|đA|đf|đ´|đ¸|đ¿|đÈ|đÖ|đà|đĽ|đŀ|đŌ|Ē%|ĒH|ĒÍ|ĒĹ|ĒĻ|ĒŁ|ĒŃ|ĒŇ|ē;|ēG|ēa|ēe|ēq|ē¶|ē»|ē÷|ēň|Ĕ"|Ĕ4|ĔÃ|Ĕý|Ĕą|ĔĆ|ĔĚ|ĔĞ|ĔĨ|ĕ"|ĕm|ĕw|ĕ¨|ĕ®|ĕÌ|ĕÑ|ĕĤ|Ė#|ĖR|Ėe|Ėu|Ė~|Ė¯|Ėĩ|ĖĬ|ėH|ė¹|ėö|ėú|ėÿ|ėĨ|Ęs|ĘÝ|Ęą|ĘČ|Ęĝ|Ęī|Ęĺ|Ęŉ|ęA|ęk|ęp|ę»|ęè|ęą|ęĐ|ęĨ|Ě'|Ě9|Ěe|Ěm|Ěo|Ě£|Ěª|Ě¾|Ěå|Ěë|Ěă|ĚĎ|ĚĜ|ĚĞ|ěP|ěx|ěê|ěî|ěö|ěĂ|ěĤ|ěĭ|ěļ|Ĝ%|ĜÜ|ĜĽ|ĝJ|ĝh|ĝ¹|ĝÃ|ĝÈ|ĝĖ|ĝĞ|ĝŇ|ĝŒ|Ğ&|Ğe|Ğs|ĞÖ|ğX|ğ²|ğ´|ğ¼|ğÙ|ğò|ğĂ|ğđ|ğĕ|ğĨ|ğĬ|ĠB|Ġc|Ġµ|ĠÈ|Ġè|Ġì|Ġđ|Ġě|ġ5|ġ<|ġH|ġm|ġº|ġÒ|ġü|ġă|ġĶ|ġŀ|Ģ;|Ģ¤|Ģ«|ĢÍ|ĢØ|Ģù|Ģă|ĢĐ|Ģđ|ģ-|ģL|ģ«|ģë|ģþ|ģċ|ģČ|ģĨ|ģĻ|Ĥf|Ĥª|Ĥñ|ĥM|ĥN|ĥU|ĥf|ĥz|ĥ»|ĥõ|ĥň|Ħ`|Ħj|Ħu|Ħ°|Ħ´|ĦÁ|ĦÈ|ĦÕ|Ħæ|ĦĤ|ħ4|ħp|ħ¡|ħ¦|ħ¶|ħß|ħç|ħĴ|ħĵ|ĨC|Ĩ°|ĨÂ|ĨÌ|Ĩç|Ĩõ|ĨĔ|Ĩŏ|ĩ8|ĩl|ĩt|ĩw|ĩċ|ĩđ|ĩĥ|ĩī|ĩŅ|Ī4|Ī9|ĪP|Īz|Ī±|ĪÅ|ĪÈ|ĪÝ|Īä|Īđ|ĪĦ|ĪĬ|ĪĽ|īb|īl|ī¥|ī¦|īÌ|īì|īČ|īĎ|īĐ|Ĭ#|Ĭ4|ĬF|Ĭ¤|Ĭê|Ĭí|Ĭû|Ĭĝ|ĬŌ|ĭ1|ĭK|ĭL|ĭz|ĭ¡|ĭ¯|ĭÌ|ĭâ|ĭĘ|ĭě|ĭĺ|ĮM|ĮR|Įd|Įx|Į¤|ĮÃ|ĮË|ĮÚ|Įå|ĮĤ|ĮĦ|Įī|į&|įD|įI|į¥|į«|įÉ|įÕ|įÛ|įĉ|įđ|įĒ|İQ|İi|İ¬|İ¾|İÕ|İ×|İĄ|İĬ|İľ|ı4|ıa|ıd|ıe|ıf|ı¡|ıĐ|ıĖ|ıĲ|Ĳ:|ĲT|ĲU|Ĳm|ĲÛ|Ĳķ|ĲŎ|ĳ0|ĳb|ĳ¢|ĳ«|ĳé|ĳí|ĳĎ|ĳĘ|ĳķ|Ĵ#|ĴF|ĴG|Ĵµ|Ĵ¹|ĴÈ|ĴÏ|Ĵý|Ĵþ|ĴĖ|ĵ8|ĵE|ĵK|ĵ¦|ĵ±|ĵÙ|ĵó|ĵõ|ĵĹ|Ķ6|ĶE|Ķl|Ķm|Ķ£|Ķ²|ĶÅ|Ķ÷|ĶĀ|Ķă|ĶĆ|ķv|ķ«|ķå|ķĢ|ķŌ|ĸ9|ĸH|ĸ¼|ĸè|ĸý|ĸĕ|ĸį|Ĺ§|Ĺ·|ĹÇ|ĹÈ|Ĺġ|Ĺĩ|ĺ#|ĺ6|ĺp|ĺr|ĺu|ĺæ|ĺí|ĺĖ|Ļ@|ĻI|Ļn|Ļ£|Ļ¶|ĻÂ|Ļú|ĻĮ|ĻŎ|ļ=|ļK|ļO|ļ_|ļ´|ļÀ|ļÄ|ļó|Ľ>|ĽC|ĽD|ĽG|ĽZ|Ľk|Ľr|Ľ¼|ĽÌ|Ľâ|ĽĮ|ĽŒ|ľf|ľÙ|ľÞ|ľĂ|ľī|ľł|ľņ|ĿÊ|Ŀď|Ŀđ|ĿĚ|Ŀĵ|ĿĻ|Ŀŏ|ŀC|ŀM|ŀ®|ŀà|ŀð|ŀõ|ŀČ|ŁE|ŁÁ|ŁÄ|Łõ|Łķ|ŁĿ|ł4|łG|łu|ł¬|łÏ|łò|łČ|łč|łĐ|łŌ|Ń6|Ń¿|ŃÅ|ŃË|ŃÚ|Ńü|Ńě|Ńņ|ń4|ń<|ńE|ńx|ń»|ńÄ|ńď|ńĺ|Ņ,|ŅP|Ņe|Ņn|Ņo|Ņ©|Ņ¯|Ņ½|ŅÛ|ŅĂ|ņî|ņð|ņô|ņĈ|ņī|ņĬ|ņı|Ň8|Ň:|ŇD|ŇT|Ň_|Ňd|Ňu|Ňª|Ňā|Ňć|ŇĈ|Ňň|ňK|ňL|ň¬|ňÇ|ňÏ|ňþ|ňĐ|ňĠ|ňŐ|ŉQ|ŉ_|ŉf|ŉÉ|ŉË|ŉĨ|ŉŃ|Ŋ0|ŊM|ŊW|ŊÔ|ŊĠ|ŋC|ŋH|ŋK|ŋÍ|ŋÒ|ŋØ|ŋÞ|ŋı|ŋĹ|Ō,|Ōl|Ō³|Ōò|Ōā|ŌĖ|ŌĚ|ŌĬ|ŌĮ|Ōĸ|ŌŒ|ōJ|ō¿|ōÀ|ōÝ|ōŉ|Ŏ8|Ŏ;|ŎQ|ŎV|Ŏ§|ŎÄ|ŎÏ|ŎĎ|ŎŇ|ŏ=|ŏD|ŏV|ŏ¹|ŏÈ|ŏÒ|ŏč|ŏĐ|ŏī|ŏĿ|ŏŉ|Ő2|Ő<|ŐC|ŐX|Őg|Ől|Őp|Ő®|Őİ|ő8|ő¹|őÀ|őó|őć|őĊ|őĖ|őĦ|őķ|őĸ|őŀ|ŒB|Œv|ŒÀ|ŒÒ|Œā|Œĉ|Œė|ŒĜ|ŒĦ|Œķ|Œľ).){255}Ň$

Tested on Regex101

 Each matched string is a Hamilton path from M to Ň.
 I know this is not secure enough. I don't know how to generate hard Hamilton path problems either. It has too many solutions. And as Martin Büttner said, Mathematica did it instantly. But this is just another NP-complete approach other than COTO's. Feel free to improve this idea and post new answers.
 The solution I have originally generated is: https://regex101.com/r/tM1vX8/2

The solution I have generated:
MĈàękÙēGâġ<øÆv:ĴÏĻĮ¤ĢùĹ·îĜĽDÂŁEā6ĶĆŌĸ¼yò¿Ĕýı¡Ë!į&qKPpzđÈ½ħ¶YÌïÁéVþèlåN2O¸úÜŐİľfćx®čńďļ=¨3d"÷ĭ¯9i'ĞsĀAÅĄ³`ðĚmĘĝŒBç¬ő¹>-ìS§nUĉňĠěĤª¾ôŅ,ĊtÊIĿĵ±RĬíăÉČĨŏĐÖĳ0°²ã1gÍáÑŉŃÚÒÇģLÐĒ%ĪĦu¦añû´~ą;ĥ»crÃ©üêºjµó5ĩċğĕwŎÄ¥ĎŋØëÎæTXėH8ņībŊÔÞÝßÀWhäĖeĲÛõÓķ«ö7QŀCōJ×¢@_ł4£FZĺ#oĂÕÿŇ

I've cracked it, but as the OP of the challenge I don't want to steal someone else's robber's score, so here's what we'll do. The MD5 hash of a permalink to a matching string is 5555e0b8b9b8c4d3c5aa4d6eac4f5249. The MD5 hash of a permalink to a non-matching string is 93fede307127da8f43d1e7a0b8cdbae1. If someone else cracks this within the 72 hour window, they'll get the credit. If not, this answer is still cracked and I'll reveal the two links giving the above hashes some time after the deadline.

@MartinBüttner: Please post your approach to crack this then. This problem at first analysis is a search for Hamilton path.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳  I don't want to spoil the fun for people who still want to crack this (and likewise, I don't want to make this free points for the first robber who comes along), so I won't give any hints before the deadline. The hashes are just to ensure that this goes down as cracked, even if I miss the 72 hour deadline with revealing the key.

@MartinBüttner: Ah, I didn't mean to ask for the solution now. Just saying that when you post the solution, please also reveal your approach. That's all.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳  Oh, of course! :)

Matches: See http://regex101.com/r/wK9hI1/1 Doesn't match:
good_job_user23013!

I imagine us being divided into 2 camps right now: those burning CPU and hoping to get lucky, and those trying to prove P=NP in a couple of days.

@WumpusQ.Wumbley And those of us using Mathematica. ;)

Since harius can't comment to elaborate how he cracked it, I'll quickly outline how I did it: the pattern indeed encodes a directed graph with 256 vertices (represented as characters) and 2270 edges (represented as pairs of characters that are allowed to be consecutive) and each match is a Hamiltonian path through that graph from M to Ň. Mathematica has a function FindHamiltonianCycle. We can turn this into a cycle that traverse Ň -> M by adding a new edge and connecting Ň and M through it. Thankfully, Mathematica finds such a cycle instantly. :)

Well, I'm 3rd, but I felt like finishing my home-grown path-finder anyway. It gave me this: http://regex101.com/r/nT2xM6/1

Would you mind posting the solution here? regex101 messed up its database settings recently and bomb all Unicode strings.

@n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳ Done.

JS-Compatible RegEx - 3,571 bytes [cracked]
I... will... have... at least... one... uncracked.... submission. o\ __ /o
[^,;]|^(.{,255}|.{257,})$|^(?!.*,;,,;;)|^(?!.*,;;,,;)|^(?!.*..,;;;,..,.)|^(?!.*.,.;.;.,.,,)|^(?!.*....,,....;;.;.;)|^(?!.*;.{8};,;;;..)|^(?!.*.{8};;.{6};,.,;)|^(?!.*..;....,.;;.{5};;...)|^(?!.*;,.;.{7},...;.{6};...)|^(?!.*...,.,..,,...,.{7};....)|^(?!.*.,;.;.{11};.{9};..,.)|^(?!.*.,.{6},....;.{11};,...,)|^(?!.*..;.{5};....,.{6};,.{12};.)|^(?!.*,,.,,.{8};.{11};.{10})|^(?!.*...,.{9};..,....;.{6},...;.{8})|^(?!.*.{6},.{8},.{6},.{8},..;.,....)|^(?!.*.{7};..;.{5},....;.{10};...;.{9})|^(?!.*..;.{7},.{5};;.{12},.{13},.)|^(?!.*.{5},..;...;.{5};..;.{6},.{22})|^(?!.*.{10},.{8},.{6},;.{14};.;.{6})|^(?!.*..,.;...,.{19};.;..;.{22})|^(?!.*.{6};..;.{14},,.{11};....,.{13})|^(?!.*.{8},.{12};.{19},.{6},;.{6},....)|^(?!.*.,.{11},...,.{7},.{16},.{11},.{6})|^(?!.*.{15};.{7};..;..,.{24},.{7},...)|^(?!.*...,,.{25};...;...;.{19},.{7})|^(?!.*.{26},....,....,.{15},.{6},.{6};....)|^(?!.*.{6};.,.{28};.{6},.{21},.;..)|^(?!.*.{21};..;..,.{22},.{21};,..)|^(?!.*.{5};.{22};,.{17};.{18},,.{8})|^(?!.*.{9};.{25};,.{20},.{6},.{14};.)|^(?!.*.,.{9},.{8};.{8};.{10};.,.{38})|^(?!.*.{18};.{8},.,.;.{5};.{6},.{41})|^(?!.*.{15},.{16};.{7};.{17};.{8};..,.{15})|^(?!.*.{18};.,.{25};..,..;.{13};.{24})|^(?!.*.{10};.{16},.{33};...;.{17},....,..)|^(?!.*.{13},.{46},.{9},.{11},,.,.{10})|^(?!.*.{14},.{33},.{18};....,.;.{16},....)|^(?!.*.{16};....;,.{8},.{30},.{31},.{6})|^(?!.*.{9},;.{15};.{22};.{30},.{16};...)|;.,,;;.;|,;,;,.,.|.;;,.;;;|;.;,,,.;|,...;.;.,,.;.|,.,.;.{5},,;|...;;....;;;;|;..,,,.;..;..|..;;,,..;.{7};.|;..,.,,...;...,...|...;;,.,.;.;.{6}|.;...;,....;.;...,|.;.{8};,.{6},.;.;|.{5},...,...;...;.;..;|...;....;..,..,.;..;...|...;.{5};,.{5},...,.;|;.,.{12},..;;.{7};|...;.{5},..;;.{9},..;.|.;,,..;.{13};....;..|.,;.{15},,...,.,..|.{8};.,....,...,..,.{9};|...;.;.{11},..,...;....;...|.,.,.{9};;....;..,.{10}|.{5};.,;....,.{15};..,|....;.{10};.;....,.{10},;...|....;.{8};;.{6},...;.{5};.{6}|..,;;.{16};....,;.{10}|.{18};.{9};,.,.,..;.|.{11},.{10};.;.;.{10};....,|....;.{11},.{10},..;.,.;.{8}|..,....,.;.{5},.{9},.{7};.{9}|.{7};.;.{5},.{13};.;.{7};...|.{5},.{15};;.{5},.{15},..;|.{12};...;..,.,..;.{5},.{17}|.{12},..;...;.{22},.,..,|.{10},.{11},.,.;.{11};;.{8}|.{11},.{9},.{5},...,.{14};.;....|;.{22};....,.;.{10};.{10};|.{13};...;.{13},.{6};.,.{10};.|.{11};....;.{17},.{9},.{5};,.|,.{14},.{12};.{6};...;.{14};...|..;.;.{19},.{16},.{5};.{6},...|.{27};..,;.{8};;.{8};.{7}|,.{6};.,.{20},.{13},.;.{11}|.{12};.{9},.{8};,.,.{17},.{10}|;.{22};..;.{5},..;....,.{22}|.{6},.{19};.{22};;,.{5};.{5}|;.{5},.{10};..;.;;.{39}|.{11};.{7};.;.{23};.{19};.;|,.{13};.{12},.,.{27};.{6},...|...;.;.{9};.{18};.;.{27},...|...;,.{12},..;.{28},.{15};..|....;.{8};..;...;.{17},.{19},.{14}|.{8};.{29};.{17};.{5};.{5};;...|...,..;.{14},.{8};.{12};.{18},.{10}|..;.;.{7};.{17},.{11},.{24},.{5}|;.{17},.;.{29};.{9};....;.{12}|.{5},..,.{6},.{16};;.{15},.{28}|...,.{12};..;.{10};.{31};.{14};|.{24},.{6},.{22},.,..,.{10};.{7}|.{10},.{12},.{5};.{12},.{7};.{23};.{8}|.{19};.,.{6},.{22},,.{7};.{22}|.{27};,.{14},..,.{7};.{15},.{12}|....;.{18},.{22},,..,.{27};....|...,.{11},.;.;.{9},.{46},.{11}|.{19},....,.{23},.{5},.{7};.{14},.{10}|.{19};,.{11};..,.{11};.{23};.{16}|.{11};.{34},.{14},.{9},.;.{13};|.{11};....,.{41},.{9};;.{8};.{14}|.{5};.;.,.{5};...;.,.{71}|.{6};.{13};....;....;.{20};.{24},.{16}|.{26};,.{19};....;.{11},.;.{26}|.{9},.{9},.{21},.{14};.{10};.{16};.{13}|.{10},.{5},.{9};.{13},...,.{24},.{28}|.{12},.{7};.{8};.{6};;.{36};.{23}|....;.{10},.{21};.{10};.{20},.{10},.{17}|.{19},.{7},.{17},.{9};.{13},.{22};.{10}|....,.{41};.{5},..,.{21};.{6};.{18}|.{25};....;.{28},.{12},.{19};.{8};.|.{10};....,.,.{22};.{11};.{44},.{5}

Resolves on virtually any string instantaneously. Testable on any JS console.
+100 rep to anyone who cracks this beast.

Challenge accepted...

Match: ThatWasActuallyFun. Non-match: ,,;,;,,;,;;;,;,;,;;,,,,;,,,;,;;,,,,,,;;,,,,;;,;,,,;,;;;;,;;,;;,;,,;,,;,;;;,;,;,;;,,,;,;;;;,;,;;;,;,,;,,,;,,,,;,;;;;;;,,,,,;,;,;;;;;,;;;,;;,,,;;;,,;,;;,,,;,,,,,,;,;,,;;,,;;,,,;,;;,,,;,,;;,;,;,;;;;,,;,;,,;;;;;,,;,,;;,,;,,;;,,,,;,,;,,;;,;;;,,,,,;,,,,,,,,;,,,,.

I'm actually rather amazed at how efficient minisat is; it took just 30 seconds to solve the problem. I started with a bruteforce approach which didn't pan out, and decided to just go with a straight SAT-solver approach (using Tseitin transformation to encode the positive constraints).

PLEASE! DON'T! BE! SO! QUICK!

dude, you're insane, this RegExp has 122 alternations, 40 of which are negative lookaheads, WTG++

@nneonneo: Lousy efficient SAT solvers. >___<  But props for transforming the problem and making use of the tools available out there. I'll award the 100 rep to one of your answers ASAP, which is about 19 hours.

PCRE - 96bytes UTF8, no delimiters, no flags
[Defeated] because nneonneo is a wise-guy
(?<Warning>[You] \Will (*FAIL)!|\So just (*SKIP)this one!|\And (*ACCEPT)defeat!|[^\d\D]{16,255})

Nothing to see here, move along...

Match: So just *SKIPthis one!; No Match: This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is not accepted. This string is still not accepted. Snow leopards FTW.

This isn't PCRE syntax; it's plain Perl syntax. (The backtracking modifiers don't work on PCRE, AFAIK)

Match: Do just this one!. Non-match: WellThatWasTooEasy. (Tested with both Perl 5.12 and Perl 5.18 on my machine)

@nneonneo correct! PS: *VERBS exist in PCRE for at least 5 years, not enough documented indeed.

@COTO the match is incorrect, NonMatch is ok.

@CSᵠ: I stand corrected! Good to know they're in PCRE, though I haven't yet seen any downstream users of PCRE document these verbs.

@CSᵠ: By the way, what was the point of [^\d\D]{16,255}? It matches nothing because [^\d\D] should be an empty character class...

@nneonneo just to spice things up a bit more

So what's up with the verbs? What do they do--in a nutshell? The regex tester I used matched on the specified input.

@COTO I used them especially because they lack proper  documentation and maybe to generate false positives (eg. like you got). You either used a nonPCRE tester or a bad/old implementation of a PCRE.

Comments start to pile up, I suggest joining RegEx room for further discussions

@COTO: http://perldoc.perl.org/perlre.html#Special-Backtracking-Control-Verbs

JS-Compatible RegEx - 733 bytes [cracked]
Let's try this a second time with the metrics reversed: a hulking regular expression but a relatively tiny key (most importantly, within the 256-byte limit).
[^a-e]|^(?:.{0,33}|.{35,}|.{11}.(?!babcde).{22}|.{17}.(?!daacde).{16}|.{23}.(?!ecacbd).{10}|.{29}.(?!ab).{4}|.{31}.(?!cd)..|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|(.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..)$

Resolves on virtually any string instantaneously. Tested on RegExr.
Expanded (for convenience):
[^a-e] |
^(?:
    .{0,33}|
    .{35,}|
    .{11}.(?!babcde).{22}|
    .{17}.(?!daacde).{16}|
    .{23}.(?!ecacbd).{10}|
    .{29}.(?!ab).{4}|
    .{31}.(?!cd)..|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).(?!\4\8\1\2\3\10|\6\3\11\2\9\1|\6\2\9\3\4\11|\8\10\6\5\3\1|\1\8\4\5\3\7).{22}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{6}.(?!\15\14\16\19\21\12|\17\12\22\13\16\15|\19\14\12\20\18\21|\16\22\19\14\20\12|\21\19\13\18\15\22).{16}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{12}.(?!\31\32\24\28\26\23|\33\25\30\29\27\32|\28\27\23\24\29\30|\31\33\23\29\26\32|\26\28\25\24\23\33).{10}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{18}.(?!\34\39|\37\38|\34\37|\36\42|\43\41|\35\38|\40\35|\44\42).{4}|
    (.)(.)(.)(.)(.)(.)(.)(.)(.)(.)(.).{20}.(?!\51\45|\53\54|\47\46|\45\54|\50\51|\53\45|\52\51|\52\48|\48\55)..
)$

Best of luck to all. ;)

Match: aaaabaaacaaadaaa, Non-match: cacdbbcabdeababcdedaacdeecacbdabcd

@user23013: I expected a crack, but not quite that quickly. Did you do it on paper?

Yes. There are only two possibilities left after the first two long expressions. And there is only one character not known after three, so I can simply try a few times to get the solution.

.NET flavor, 60 bytes [cracked]
^((\d)(?!(|(\d\d)*\d|(\d{3})*\d\d|(\d{5})*\d{4}|\d{6})\2))+$

Tested with Regex Storm.

Match: 1234567890０12345. Non-match: 1111222233334444.

٠߀०০੦૦୦௦౦೦൦๐໐༠၀႐០᠐᥆᧐᭐᮰᱀᱐꘠꣐꤀꩐０ So these are all considered digits in .NET...

That's insane, half of those aren't even showing up right in my browser

Python flavour: 211 bytes [cracked]
Note: This answer was posted before the rule change about maximum key length
Thought I'd get the ball rolling with this:
(((((((((((((((\)\\\(58\)5\(58\(\\5\))\15\)9)\14\\919\)\)4992\)5065\14\(5)\13\\\14\\71\13\(\13\)4\\\13\\)\12\12\\28\13)\11)\10\\7217)\9\\)\8\\04)\7\)\(\8\()\6\(183)\5)\4\)65554922\\7624\)7)\3\)8\(0)\2\4\\8\\8)\1

(Tested on RegExr)

Simple backreference explosion of the characters \()0123456789

I can tell you that the accepted string is approx. 7 million characters in length. As for actually representing it somehow, maybe a 7 MB text file somewhere?

Yeah, that's pretty much the only way to go. I thought I'd start off with something that isn't hard to decipher, but the trick was with output generation. If the minute limit wasn't in place though this would have been much longer :P

Entering what I believe is the only string that matches your regex at RegExr.com reliably crashes my Chrome browser. In Safari it works but RegExr reports a 'timeout'. Have you successfully tested it online?

@Emil I tested it successfully in Firefox. And I'm still waiting to save it.

Hm... well it worked when I tried in Chrome...

The key is 5281064 bytes by my count. Uploaded file here (5 mb) http://www.mediafire.com/view/4jt41pzfp7855ax/match.txt

@stokastic Access denied? You might be able to put it in a gist on GitHub. (Also, technically, a key consists of two strings, but it shouldn't be hard to find a 16-character string that the regex doesn't match. ;))

@MartinBüttner strange, permissions were set to public. Try here (link will only last a few hours probably): https://www.sendspace.com/file/ghas25 . And here is a string that it doesn't match ;) "abcdef0123456789"

@stokastic Yep, you got it :)

JS-Compatible RegEx - 12,371 bytes [cracked]
After some encouragement by Martin, and seeing that other cops are happily submitting 600+ KB regexes, I decided to take the plunge once more with this (and prettified version here).
Resolves on virtually any string instantaneously. Testable on any JS console. Unfortunately the size makes it untestable by many online regex testers.

Ahaha I'll try not to go nuts with the regex sizes - this challenge is hard though :/ incriminates @user23013

Match: this was not NP-hard. Non-match: nerdnydeprdoypoypwwwdprelwsprwssddayaeeeysyaaaypowroplsaoprdaolasnoylaeaeadeosladnnosyoywyesorlrydwddadoeyponneeyaaapesenaalnneydaewndplredlerwaawlnrssapapaopnrdwnslowdoanlrernpwyyarpprwnrssdlaopsnnrnnnardpaessldalroleswnnooarlpllasapsesaorardwreylayrr

I just bruteforced it completely (took ~0.06 seconds in Python) and obtained four admissible solutions, but due to a bug in your regex, your regex rejects many more solutions. (Basically, you don't check that every character in a given "substring" gets used, and you don't check that a "substring" only consists of 84 characters)

(Final note: http://regexpal.com/ handles this regex just fine; I'm guessing it probably just uses the browser's regex engine).

With 12k bytes there's no need to link to an external source. SE answers can have up to 30k characters.

Dang it. Back to the drawing board. >___< @MartinBüttner: My browser was hanging while SE was trying to format the code, so I figured I'd leave it out.

.NET flavor, 458 bytes [cracked]
^(?=[01]{10},[01]{10}$)(0|1((?<=^.)(?<l>){512}|(?<=^..)(?<l>){256}|(?<=^...)(?<l>){128}|(?<=^.{4})(?<l>){64}|(?<=^.{5})(?<l>){32}|(?<=^.{6})(?<l>){16}|(?<=^.{7})(?<l>){8}|(?<=^.{8})(?<l>){4}|(?<=^.{9})(?<l>){2}|(?<=^.{10})(?<l>){1})(?(l)(?<-l>(?=.*,(?:0|1(?<m>){512})(?:0|1(?<m>){256})(?:0|1(?<m>){128})(?:0|1(?<m>){64})(?:0|1(?<m>){32})(?:0|1(?<m>){16})(?:0|1(?<m>){8})(?:0|1(?<m>){4})(?:0|1(?<m>){2})(?:0|1(?<m>){1})$))|){1024})*,(?<-m>){669043}(?(m)(?!)|)

This one is easy. But I'll post a harder one later.
I think I'm pretty near the cryptographically secure answer.
Tested on RegexStorm.

 This is basically about integer factorization. The matched string should be the binary representation of two integers A and B. For each 1 from A, it will match 512, 256, ..., 1 times group l, which can be added to get A. And for each time l, it will match B using lookahead, and B times group m which is similar to A times l. So m is matched a total of A*B times. Finally it removes the group m 669043 times and checks if there is no more m. So A*B must be exactly 669043.

 For simplicity: 669043 = 809 * 827 and the solution is the binary form of these two numbers.

 This method doesn't work with too big numbers to make it secure, because the Regex engine has to increase the number that many times. But I have posted a new answer to work with base 289 big integers. It has a 1536 bit long product.

 Also thanks Martin Büttner for introducing the balancing group feature of .NET Regex in his answer.

This idea, wow...

Match: 1100101001,1100111011. Non-match: ThatsWhatIWantedToDo,Nice

I think the only problem is that the match takes exponentially long, and that the target integer has to be expressed as a repeat count (so it is most likely limited to 32/64/128 bits, which are all trivial to factor). I have some ideas on surpassing these limitations using Karatsuba multiplication, but then I get log(n)^2 sized regexes...

@user23013 I really like the way you used empty strings here - seems like you could probably do something like this: http://pastebin.com/c2wCK8fU (But I can't seem to get it to work without hardcoding in the numbers 11 and 13)

@Sp3000 http://pastebin.com/SW0YbQar This works. I'm not sure why. Perhaps its developer thinks matching empty strings repeatedly doesn't make sense.

Oh nice, that fixes it nicely. Too bad, as @nneonneo has pointed out, repeat counts are going to be a limitation though :/

http://pastebin.com/vXq8QwAr Anything above 3 digits times out - I'm disappointed :(

@Sp3000: not at all a surprise; you're basically asking the regex engine to count to 800000+. This is going to be really slow (especially when the "counting" is done via a regular expression evaluator virtual machine).

JS-Compatible RegEx - 2,447 bytes [cracked]
My final attempt.
I'm holding out hope that this one lasts at least a few hours before being cracked. After that, I give up. :P
[^a-f]|^(?:.{0,51}|.{53,}|.{11}.(?!d).{40}|.{12}.(?!a).{39}|.{13}.(?!a).{38}|.{14}.(?!f).{37}|.{15}.(?!d).{36}|.{16}.(?!a).{35}|.{17}.(?!d).{34}|.{18}.(?!c).{33}|.{19}.(?!f).{32}|.{20}.(?!d).{31}|.{21}.(?!d).{30}|.{22}.(?!d).{29}|.{23}.(?!f).{28}|.{24}.(?!d).{27}|.{25}.(?!b).{26}|.{26}.(?!f).{25}|.{27}.(?!f).{24}|.{28}.(?!e).{23}|.{29}.(?!c).{22}|.{30}.(?!c).{21}|.{31}.(?!b).{20}|.{32}.(?!d).{19}|.{33}.(?!e).{18}|.{34}.(?!c).{17}|.{35}.(?!a).{16}|.{36}.(?!a).{15}|.{37}.(?!e).{14}|.{38}.(?!b).{13}|.{39}.(?!f).{12}|.{40}.(?!d).{11}|.{41}.(?!f).{10}|.{42}.(?!c).{9}|.{43}.(?!f).{8}|.{44}.(?!e).{7}|.{45}.(?!c).{6}|.{46}.(?!b).{5}|.{47}.(?!b).{4}|.{48}.(?!f).{3}|.{49}.(?!a).{2}|.{50}.(?!d).{1}|....(.)(.)(.).....(?!\1|\2|\3).{40}|.(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|(.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|(.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|.(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|.(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|(.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|(.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|(.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|(.)(.)(.).........{17}.(?!\52|\53|\54).{23}|.(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|(.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|.......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|.(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|.(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|(.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|.....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|(.).(.).(.).......{28}.(?!\85|\86|\87).{12}|..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|(.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|.(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|....(.)(.)....(.).{39}.(?!\118|\119|\120).{1})$

Like all previous submissions, it resolves instantaneously. Unlike previous submissions, it's too long for RegExr.
Expanded:
[^a-f]|
^(?:
    .{0,51}|
    .{53,}|
    .{11}.(?!d).{40}|
    .{12}.(?!a).{39}|
    .{13}.(?!a).{38}|
    .{14}.(?!f).{37}|
    .{15}.(?!d).{36}|
    .{16}.(?!a).{35}|
    .{17}.(?!d).{34}|
    .{18}.(?!c).{33}|
    .{19}.(?!f).{32}|
    .{20}.(?!d).{31}|
    .{21}.(?!d).{30}|
    .{22}.(?!d).{29}|
    .{23}.(?!f).{28}|
    .{24}.(?!d).{27}|
    .{25}.(?!b).{26}|
    .{26}.(?!f).{25}|
    .{27}.(?!f).{24}|
    .{28}.(?!e).{23}|
    .{29}.(?!c).{22}|
    .{30}.(?!c).{21}|
    .{31}.(?!b).{20}|
    .{32}.(?!d).{19}|
    .{33}.(?!e).{18}|
    .{34}.(?!c).{17}|
    .{35}.(?!a).{16}|
    .{36}.(?!a).{15}|
    .{37}.(?!e).{14}|
    .{38}.(?!b).{13}|
    .{39}.(?!f).{12}|
    .{40}.(?!d).{11}|
    .{41}.(?!f).{10}|
    .{42}.(?!c).{9}|
    .{43}.(?!f).{8}|
    .{44}.(?!e).{7}|
    .{45}.(?!c).{6}|
    .{46}.(?!b).{5}|
    .{47}.(?!b).{4}|
    .{48}.(?!f).{3}|
    .{49}.(?!a).{2}|
    .{50}.(?!d).{1}|
    ....(.)(.)(.).....(?!\1|\2|\3).{40}|
    .(.).(.)..(.).....{1}.(?!\4|\5|\6).{39}|
    ...(.)(.).....(.).{2}.(?!\7|\8|\9).{38}|
    ......(.)(.).(.)..{3}.(?!\10|\11|\12).{37}|
    ....(.)(.)(.).....{4}.(?!\13|\14|\15).{36}|
    ..(.)(.)(.).......{5}.(?!\16|\17|\18).{35}|
    (.).(.)......(.)..{6}.(?!\19|\20|\21).{34}|
    ..(.).....(.).(.).{7}.(?!\22|\23|\24).{33}|
    (.)..(.)(.).......{8}.(?!\25|\26|\27).{32}|
    ...(.).....(.)(.).{9}.(?!\28|\29|\30).{31}|
    .(.)(.).....(.)...{10}.(?!\31|\32|\33).{30}|
    .(.)...(.)..(.)...{11}.(?!\34|\35|\36).{29}|
    (.)(.).....(.)....{12}.(?!\37|\38|\39).{28}|
    ...(.).(.).(.)....{13}.(?!\40|\41|\42).{27}|
    ..(.)(.)..(.).....{14}.(?!\43|\44|\45).{26}|
    (.).(.)....(.)....{15}.(?!\46|\47|\48).{25}|
    (.)..(.)...(.)....{16}.(?!\49|\50|\51).{24}|
    (.)(.)(.).........{17}.(?!\52|\53|\54).{23}|
    .(.)..(.)(.)......{18}.(?!\55|\56|\57).{22}|
    (.)...(.)..(.)....{19}.(?!\58|\59|\60).{21}|
    .......(.)(.)(.)..{20}.(?!\61|\62|\63).{20}|
    .(.).....(.).(.)..{21}.(?!\64|\65|\66).{19}|
    ..(.)..(.)...(.)..{22}.(?!\67|\68|\69).{18}|
    ..(.).(.).....(.).{23}.(?!\70|\71|\72).{17}|
    ...(.).(.)..(.)...{24}.(?!\73|\74|\75).{16}|
    .(.)(.)(.)........{25}.(?!\76|\77|\78).{15}|
    (.).(.).....(.)...{26}.(?!\79|\80|\81).{14}|
    .....(.)..(.).(.).{27}.(?!\82|\83|\84).{13}|
    (.).(.).(.).......{28}.(?!\85|\86|\87).{12}|
    ..(.)...(.)..(.)..{29}.(?!\88|\89|\90).{11}|
    (.)....(.)..(.)...{30}.(?!\91|\92|\93).{10}|
    ....(.).(.).(.)...{31}.(?!\94|\95|\96).{9}|
    ...(.)..(.)(.)....{32}.(?!\97|\98|\99).{8}|
    ..(.)..(.)..(.)...{33}.(?!\100|\101|\102).{7}|
    ..(.).(.)(.)......{34}.(?!\103|\104|\105).{6}|
    ..(.)(.)..(.).....{35}.(?!\106|\107|\108).{5}|
    .(.).....(.)(.)...{36}.(?!\109|\110|\111).{4}|
    ..(.)....(.)(.)...{37}.(?!\112|\113|\114).{3}|
    ...(.)..(.)...(.).{38}.(?!\115|\116|\117).{2}|
    ....(.)(.)....(.).{39}.(?!\118|\119|\120).{1}
)$

Match: aaaabaaacaaadaaa. Non-match: fdeacdbfbdcadaafdadcfdddfdbffeccbdecaaebfdfcfecbbfad.

Replace (.) with the matching character, and sort by that character, and it will become obvious.

Note that this is NP-complete, but not cryptographically secure. And there are too many restrictions and too few variables to make it difficult.

@user23013: Well played, sir. ;) And indeed I believe this is reducible to SAT, which was my intent. Just not enough bits in there to make it difficult, as you say.

Python flavour (721 bytes) [cracked]
It's time for "Parsing Problem v2":
^(((?(8)S)(((?(9)I|\\)(?(3)\]|Z)((?(7)l|R)(((((((?(4)p)((?(7)x)(?(1)B|Z)(?(11)\()(?(9)X)(?(8)P|T)(?(6)a|E)((?(5)E)(((?(8)3|\[)((?(3)\(|1)((?(1)M|L)(?(3)v|b)(?(2)t|l)(?(1)q)(?(1)K|H)(?(2)\)|R)(?(3)O|K)(?(5)l|l)(((?(2)\[|3)((?(2)N)((?(2)\\)((?(1)E|\])(?(1)\[)([(?(1)Q)])(?(24)\[)(?(24)q))(?(24)g))(?(22)s|U)(?(22)H)(?(23)c|U))(?(24)Q)(?(24)Q)(?(24)H)(?(23)K|\[))(?(22)e|y))(?(24)\\)(?(21)P|4)(?(19)T)(?(24)\))))(?(24)M)(?(17)\()(?(24)2))(?(19)7)(?(21)t|X)(?(22)v))(?(24)\[)(?(19)A|L)(?(16)E|1))(?(19)1|c)(?(14)K|\\)(?(19)4|5)(?(24)\\)(?(20)r)))(?(24)B)(?(24)w)(?(24)5))(?(24)\())(?(24)\\))(?(24)T))(?(9)\[))(?(15)z|w))(?(24)K)\7F(?(24)m)(?(24)R))(?(24)\[))(?(24)h))(?(14)x|t)(?(3)R|M)(?(24)\])(?(24)w))(?(21)z|6)(?(16)r)()$

Tested on Regex101.

 This regex is effectively "hide a tree in a forest". The bulk of the
 regex consists of (?(id)yes-pattern|no-pattern) expressions, which
 match the appropriate pattern depending on whether or not a group
 with the specified id exists. Most of these expressions do not
 contribute to the key, but some do.

 However, not-so-subtly hidden in the regex was [(?(1):Q)] which is
 actually a character set, and \7, which requires you to keep track
 of the groups somehow. Both of these will show up on any editor with
 highlighting, but were meant to trip up anyone who wasn't cautious.

Man, this is gonna take some work.

\ZRZTE[1LblHRKl3]?sHcKePT(7tvAE1K4r[zZTE[1LblHRKl3]?sHcKePT(7tvAE1K4rFxRzr matches.  a doesn't match

Additionally, the set of all possible matches is (my previous comment) with both of the ?'s replaced with any character in (?(1)Q)

(on Regex101, it tells you exactly what it was trying to match when the match failed.  This made finding the matching stuff somewhat easier (at least for spotting typos in my solution)).

I was close, I was just missing the ?'s

I got \ZRZTE[1LblHRKl3]1sHcKePT(7tvAE1K4r[zZTE[1LblHRKl3]1sHcKePT(7tvAE1K4rFxRzr there was no ? in mine? why? aaaaaaaaaaaaaaaa doesn't match

Ah I see it. Somehow I missed the ? in the `[(?(1)Q)]

Nice! I didn't expect it go down that quickly (I was hoping human error would hinder progress but I guess you guys are just too good at being careful :) )

@g.rocket Your key isn't technically valid, because both strings need to have 16 characters, but since almost everything fails the string, I'll accept that as successful cracking. ;)

Perl flavor, 133 [cracked]
Okay, this one should be harder to brute force:
^([^,]{2,}),([^,]{2,}),([^,]{2,}),(?=.\2+,)(?=.\3+,)\1+,(?=.\1+,)(?=.\3+,)\2+,(?=.\1+,)(?=.\2+,)\3+,(?=.{16,20}$)(\1{3}|\2{3}|\3{3})$

And a longer version, not part of the challenge:
^([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),([^,]{3,}),(?=.\2+,)(?=.\3+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\1+,(?=.\1+,)(?=.\3+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\2+,(?=.\1+,)(?=.\2+,)(?=.\4+,)(?=.\5+,)(?=.\6+,)\3+,(?=.\1+,)(?=.\2+,)(?=.\3+,)(?=.\5+,)(?=.\6+,)\4+,(?=.\1+,)(?=.\2+,)(?=.\3+,)(?=.\4+,)(?=.\6+,)\5+,(?=.\1+$)(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)\6+$

Can be tested on Regex101 (pcre flavor).

 The idea behind this pattern is that we can encode a simple system of
 congruence equations in a regex using lookaheads. For example, the
 regex ^(?=(..)*$)(...)*$ matches any string whose length is a common
 multiple of 2 and 3, that is, a multiple of 6. This can be seen
 as the equation 2x ≡ 0 mod 3. We can parameterize the equation using
 capture groups: the regex ^(.*),(.*),(?=\1*$)\2*$ matches strings
 where the number of characters after the last comma is a common
 multiple of the length of the first and second submatches. This can be
 seen as the parameterized equation ax ≡ 0 mod b, where a and b
 are the lengths of the two submatches.  The above regex begins
 by taking three "parameters" of length at least two, and is followed
 by three "systems of equations" of the from (?=.\1+,)(?=.\2+,)\3+, that
 correspond to {ax + 1 ≡ 0 mod c, by + 1 ≡ 0 mod c, ax = by}, where
 a, b and c are the lengths of the corresponding submatches. This system of equations has a solution if and only if a and b are
 coprime to c. Since we have three such systems, one for each
 submatch, the lengths of the submatches must be pairwise coprime.
  The last part of the regex is there to ensure that one of the
 submatches is of length 6. This forces the other two submatches to
 be 5 and 7 characters long, since any smaller values won't be
 coprime and any larger values will result in a key longer than 256
 characters. The smallest solutions to the equations then yield
 substrings of lengths 85, 36 and 91, which result in a string of length 254---about as long as we can get.  The longer regex
 uses the same principle, only with 6 parameters of length at least three
 and no additional restrictions. The smallest pairwise coprime set of
 six integers greater than 2 is {3, 4, 5, 7, 11, 13}, which yields
 substrings of minimal lengths 40041, 15016, 24025, 34321, 43681 and 23101. Therefore,
 the shortest string that matches the longer regex is
 a{3},a{4},a{5},a{7},a{11},a{13},a{40041},a{15016},a{24025},a{34321},a{43681},a{23101}
 (up to the order of parameters.) That's 180,239 characters!

That {16,20}.

Match: aaaaa,aaaaaa,aaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaa, Mismatch: aaaaaaaaaaaaaaaa

I think SE keeps adding extra as for some reason - there should be 5,6,7,85,36,91,18 as between the commas :/

@Sp3000 Pick a card, any card ;) Yeah, you cracked it. It seems like some of the 'a's in your comment are non-ASCII, but the numbers are right.

@Ell The as are all ASCII, but there are two non-printable Unicode characters for each manual line break SE does.

Python flavour (4842 bytes) [cracked]
With thanks to @COTO for ideas and advice
I liked @COTO's 3-SAT idea so much that I thought I'd try to make my own regex based off it. I'm not that familiar with the theoretics of 3-SAT though, so I'm just going to pray to the RNG gods and hope I have enough restrictions in place.
I tried to keep the regex under 5000 characters to be fair - obviously longer regexes would be impossible to crack, but they wouldn't be very fun to crack either.
[^01]|^(.{0,81}|.{83,}|....0.{10}1.{22}0.{43}|....0.{14}0.{35}0.{26}|....0.{16}0.{5}1.{54}|....0.{17}1.{34}0.{24}|....1.{11}0.{41}1.{23}|....1.{12}1.{27}1.{36}|....1.{22}1.{38}1.{15}|....1.{30}0.{35}1.{10}|....1.{46}0.1.{28}|....1.{6}1.{65}0....|...0....1.1.{71}|...0.{18}0.{23}0.{35}|...1.{11}1.{33}1.{32}|..0...0.{53}1.{21}|..0.{30}1.{17}0.{30}|..1.{41}0.{10}0.{26}|.0.{13}0.{39}1.{26}|.0.{18}0.{49}0.{11}|.0.{27}1.{36}0.{15}|.0.{31}11.{47}|.00.{37}1.{41}|.1.{32}0.{31}1.{15}|.1.{38}0.{25}0.{15}|.1.{7}0.{38}0.{33}|.{10}0.{14}0.{15}0.{40}|.{10}0.{15}1.{15}1.{39}|.{10}0.{27}1.{11}1.{31}|.{10}0.{39}0.{7}0.{23}|.{10}0.{42}10.{27}|.{10}0.{9}0.{38}0.{22}|.{10}1.{45}1.{16}0.{8}|.{10}1.{47}0.{15}0.{7}|.{10}1.{59}0.{5}1.{5}|.{11}0.{11}0.{54}0...|.{11}0.{29}1.{35}0....|.{11}1.{32}0.{25}1.{11}|.{11}1.{48}1.{6}1.{14}|.{11}11.{50}1.{18}|.{12}0.{27}1.{18}0.{22}|.{12}0.{45}1.{7}1.{15}|.{12}1.{15}0.{42}1.{10}|.{13}0.{40}1...0.{23}|.{13}1.{20}1.{5}1.{41}|.{13}1.{22}0.{31}0.{13}|.{13}1.{24}1.{39}1...|.{13}1.{58}0.{8}0|.{14}0.{22}0....1.{39}|.{14}0.{23}0.{23}1.{19}|.{14}0.{53}10.{12}|.{14}1.{19}1.{11}0.{35}|.{14}1.{19}1.{21}1.{25}|.{14}1.{23}0.{14}0.{28}|.{14}1.{24}1.{12}1.{29}|.{14}1.{35}0.{22}0.{8}|.{14}1.{48}0.{15}1..|.{14}1.{58}0....1...|.{14}1.{65}11|.{14}1.{6}1.0.{58}|.{15}0...01.{61}|.{15}0.{12}0.{30}0.{22}|.{15}0.{15}0.{34}0.{15}|.{15}0.{30}1.{25}0.{9}|.{15}0.{31}0.{32}1.|.{15}0.{36}0.{25}1...|.{15}1.{14}1.{21}1.{29}|.{15}1.{16}1.{16}1.{32}|.{15}1.{20}0.{32}1.{12}|.{16}0.{35}1.{24}0....|.{16}0.{36}1.{15}1.{12}|.{16}1.{13}1.{22}0.{28}|.{16}1.{16}1.{14}0.{33}|.{16}1.{48}1.0.{14}|.{17}1.{29}1.{31}0..|.{17}1.{47}1.{8}0.{7}|.{17}1.{9}0.{20}0.{33}|.{18}0..0.{59}1|.{18}0.{33}1.{6}0.{22}|.{18}0.{36}1.{24}1.|.{18}0.{39}0.{17}1.{5}|.{18}1..0.{35}0.{24}|.{18}1.{16}0.{7}1.{38}|.{19}0.{17}0.{8}1.{35}|.{19}1.{42}00.{18}|.{20}0.{25}1.{31}1...|.{20}0.{43}1.{12}0....|.{20}0.{8}1.{40}0.{11}|.{20}00.{56}1...|.{20}1.{38}0.{7}1.{14}|.{21}0.{39}1.{16}0...|.{22}1....0.{44}1.{9}|.{22}1..1.{20}1.{35}|.{23}0.{39}1.{8}0.{9}|.{23}0.{8}1.{41}1.{7}|.{23}1.{18}1.{25}0.{13}|.{23}1.{20}0.{6}0.{30}|.{24}0.{17}1.{16}0.{22}|.{24}0.{21}1.{13}0.{21}|.{24}1...1.{49}0...|.{24}1.{5}0.{37}0.{13}|.{24}1.{8}1.{37}0.{10}|.{25}0.{36}0....0.{14}|.{25}1....0.{29}0.{21}|.{25}1....1.{10}1.{40}|.{25}1.{13}1.{13}0.{28}|.{25}1.{40}0.{7}0.{7}|.{26}0.{13}1.{21}0.{19}|.{26}0.{13}1.{25}1.{15}|.{27}0.{20}1.{11}0.{21}|.{27}0.{36}0.{6}0.{10}|.{27}1....1.0.{47}|.{27}1...0.{13}1.{36}|.{27}1.{10}0.{26}0.{16}|.{27}1.{30}1.{15}0.{7}|.{28}0.{14}1.{37}0|.{28}0.{21}1.0.{29}|.{28}0.{26}0.{16}0.{9}|.{28}1.{18}1.{23}1.{10}|.{29}0.{17}0.0.{32}|.{29}1.{24}0.{19}1.{7}|.{29}1.{46}1....0|.{30}1.{18}1.{9}0.{22}|.{30}1.{28}0....1.{17}|.{32}0.{25}1.{6}1.{16}|.{33}0.{22}1.{12}0.{12}|.{33}0.{6}0.{11}0.{29}|.{33}1.{5}1.{31}0.{10}|.{34}0.{13}0.{8}0.{24}|.{34}1...1.{35}0.{7}|.{34}1..1.{29}1.{14}|.{34}1.{38}01.{7}|.{34}1.{5}0.{40}1|.{34}1.{6}1.{38}1.|.{34}1.{7}0.{31}0.{7}|.{34}11...1.{42}|.{35}0.{19}0..0.{23}|.{35}1.{12}1.{24}0.{8}|.{36}0.{6}1.{17}1.{20}|.{36}0.{7}1.{17}1.{19}|.{36}0.{8}0.{13}1.{22}|.{36}1.{14}0.{9}1.{20}|.{37}0.{26}1.{16}0|.{37}1.{27}0.{10}0.{5}|.{38}1.{21}1.{7}1.{13}|.{39}0..0.{20}0.{18}|.{39}0.{15}0.{19}1.{6}|.{40}0....0.{28}1.{7}|.{40}0.{15}1.0.{23}|.{40}0.{5}1.{16}0.{18}|.{40}0.{8}1.{29}1..|.{40}00.0.{38}|.{41}0.0.{20}0.{17}|.{41}00.{32}0.{6}|.{41}1.{16}1.{21}1.|.{41}1.{8}1.{18}0.{12}|.{42}1.{31}1.{6}1|.{42}11.{27}0.{10}|.{43}0.{34}10..|.{44}1.0.{10}1.{24}|.{45}0.{9}0.{5}0.{20}|.{45}1.{12}0.{22}1|.{45}1.{17}1....0.{13}|.{45}1.{9}0...0.{22}|.{46}0.{11}1.{19}1...|.{46}1.{24}0.{5}0....|.{47}11.{8}1.{24}|.{48}0.{12}1....0.{15}|.{48}0.{15}0.{13}1...|.{48}1...0.{13}0.{15}|.{48}1.{11}0..0.{18}|.{48}11.{21}0.{10}|.{49}1.{7}1.{14}0.{9}|.{51}1.{12}1.{5}1.{11}|.{54}0.{13}0.{6}1.{6}|.{54}1.{11}1.1.{13}|.{56}0.{16}0..1.{5}|.{56}1.{11}0.{6}0.{6}|.{58}1....1.{6}0.{11}|.{5}0.{17}0.{42}0.{15}|.{5}0.{23}1.{26}1.{25}|.{5}0.{34}1.{22}0.{18}|.{5}0.{6}1.{13}1.{55}|.{5}1.{12}0.{31}1.{31}|.{5}1.{16}0.{39}1.{19}|.{5}1.{16}1.1.{57}|.{5}1.{24}1.{15}1.{35}|.{5}1.{24}1.{47}1...|.{66}0.0.{5}1.{7}|.{6}0....1.{24}0.{45}|.{6}0.{19}0.{7}1.{47}|.{6}0.{23}0.{14}0.{36}|.{6}0.{25}1.{41}0.{7}|.{6}0.{46}1.{22}0.{5}|.{6}0.{52}11.{21}|.{6}1.{35}10.{38}|.{7}0.{20}0.{16}0.{36}|.{7}0.{34}1.{20}1.{18}|.{7}0.{6}0.{36}0.{30}|.{7}0.{7}0.{15}0.{50}|.{7}0.{8}1.{42}1.{22}|.{7}1.{5}1.{56}1.{11}|.{7}1.{67}0..1...|.{8}0.{10}0.{38}0.{23}|.{8}0.{41}11.{30}|.{8}0.{9}1.{37}1.{25}|.{8}1.{50}1.{14}1.{7}|.{9}0..1.{55}0.{13}|.{9}0.{21}1.{42}0.{7}|.{9}0.{59}00.{11}|.{9}0.{9}0....1.{57}|.{9}00.{41}1.{29}|.{9}1....0.{20}0.{46}|.{9}1...0.{41}1.{26}|.{9}1.{30}0.{16}1.{24}|.{9}1.{30}0.{37}1...|.{9}1.{30}1.{14}1.{26}|.{9}1.{40}01.{30}|0.{17}1.{34}0.{28}|0.{23}1.{43}1.{13}|0.{30}1.{26}1.{23}|1.{13}00.{66}|1.{28}0.{42}1.{9}|1.{36}0.{35}1.{8}|1.{42}1.{32}1.{5}|1.{49}0.{16}0.{14}|1.{52}0.{7}0.{20}|)$

And here it is in a form that's a bit easier to read:
[^01]|
^(
  .{0,81}|
  .{83,}|
  ....0.{10}1.{22}0.{43}|
  ....0.{14}0.{35}0.{26}|
  ....0.{16}0.{5}1.{54}|
  ....0.{17}1.{34}0.{24}|
  ....1.{11}0.{41}1.{23}|
  ....1.{12}1.{27}1.{36}|
  ....1.{22}1.{38}1.{15}|
  ....1.{30}0.{35}1.{10}|
  ....1.{46}0.1.{28}|
  ....1.{6}1.{65}0....|
  ...0....1.1.{71}|
  ...0.{18}0.{23}0.{35}|
  ...1.{11}1.{33}1.{32}|
  ..0...0.{53}1.{21}|
  ..0.{30}1.{17}0.{30}|
  ..1.{41}0.{10}0.{26}|
  .0.{13}0.{39}1.{26}|
  .0.{18}0.{49}0.{11}|
  .0.{27}1.{36}0.{15}|
  .0.{31}11.{47}|
  .00.{37}1.{41}|
  .1.{32}0.{31}1.{15}|
  .1.{38}0.{25}0.{15}|
  .1.{7}0.{38}0.{33}|
  .{10}0.{14}0.{15}0.{40}|
  .{10}0.{15}1.{15}1.{39}|
  .{10}0.{27}1.{11}1.{31}|
  .{10}0.{39}0.{7}0.{23}|
  .{10}0.{42}10.{27}|
  .{10}0.{9}0.{38}0.{22}|
  .{10}1.{45}1.{16}0.{8}|
  .{10}1.{47}0.{15}0.{7}|
  .{10}1.{59}0.{5}1.{5}|
  .{11}0.{11}0.{54}0...|
  .{11}0.{29}1.{35}0....|
  .{11}1.{32}0.{25}1.{11}|
  .{11}1.{48}1.{6}1.{14}|
  .{11}11.{50}1.{18}|
  .{12}0.{27}1.{18}0.{22}|
  .{12}0.{45}1.{7}1.{15}|
  .{12}1.{15}0.{42}1.{10}|
  .{13}0.{40}1...0.{23}|
  .{13}1.{20}1.{5}1.{41}|
  .{13}1.{22}0.{31}0.{13}|
  .{13}1.{24}1.{39}1...|
  .{13}1.{58}0.{8}0|
  .{14}0.{22}0....1.{39}|
  .{14}0.{23}0.{23}1.{19}|
  .{14}0.{53}10.{12}|
  .{14}1.{19}1.{11}0.{35}|
  .{14}1.{19}1.{21}1.{25}|
  .{14}1.{23}0.{14}0.{28}|
  .{14}1.{24}1.{12}1.{29}|
  .{14}1.{35}0.{22}0.{8}|
  .{14}1.{48}0.{15}1..|
  .{14}1.{58}0....1...|
  .{14}1.{65}11|
  .{14}1.{6}1.0.{58}|
  .{15}0...01.{61}|
  .{15}0.{12}0.{30}0.{22}|
  .{15}0.{15}0.{34}0.{15}|
  .{15}0.{30}1.{25}0.{9}|
  .{15}0.{31}0.{32}1.|
  .{15}0.{36}0.{25}1...|
  .{15}1.{14}1.{21}1.{29}|
  .{15}1.{16}1.{16}1.{32}|
  .{15}1.{20}0.{32}1.{12}|
  .{16}0.{35}1.{24}0....|
  .{16}0.{36}1.{15}1.{12}|
  .{16}1.{13}1.{22}0.{28}|
  .{16}1.{16}1.{14}0.{33}|
  .{16}1.{48}1.0.{14}|
  .{17}1.{29}1.{31}0..|
  .{17}1.{47}1.{8}0.{7}|
  .{17}1.{9}0.{20}0.{33}|
  .{18}0..0.{59}1|
  .{18}0.{33}1.{6}0.{22}|
  .{18}0.{36}1.{24}1.|
  .{18}0.{39}0.{17}1.{5}|
  .{18}1..0.{35}0.{24}|
  .{18}1.{16}0.{7}1.{38}|
  .{19}0.{17}0.{8}1.{35}|
  .{19}1.{42}00.{18}|
  .{20}0.{25}1.{31}1...|
  .{20}0.{43}1.{12}0....|
  .{20}0.{8}1.{40}0.{11}|
  .{20}00.{56}1...|
  .{20}1.{38}0.{7}1.{14}|
  .{21}0.{39}1.{16}0...|
  .{22}1....0.{44}1.{9}|
  .{22}1..1.{20}1.{35}|
  .{23}0.{39}1.{8}0.{9}|
  .{23}0.{8}1.{41}1.{7}|
  .{23}1.{18}1.{25}0.{13}|
  .{23}1.{20}0.{6}0.{30}|
  .{24}0.{17}1.{16}0.{22}|
  .{24}0.{21}1.{13}0.{21}|
  .{24}1...1.{49}0...|
  .{24}1.{5}0.{37}0.{13}|
  .{24}1.{8}1.{37}0.{10}|
  .{25}0.{36}0....0.{14}|
  .{25}1....0.{29}0.{21}|
  .{25}1....1.{10}1.{40}|
  .{25}1.{13}1.{13}0.{28}|
  .{25}1.{40}0.{7}0.{7}|
  .{26}0.{13}1.{21}0.{19}|
  .{26}0.{13}1.{25}1.{15}|
  .{27}0.{20}1.{11}0.{21}|
  .{27}0.{36}0.{6}0.{10}|
  .{27}1....1.0.{47}|
  .{27}1...0.{13}1.{36}|
  .{27}1.{10}0.{26}0.{16}|
  .{27}1.{30}1.{15}0.{7}|
  .{28}0.{14}1.{37}0|
  .{28}0.{21}1.0.{29}|
  .{28}0.{26}0.{16}0.{9}|
  .{28}1.{18}1.{23}1.{10}|
  .{29}0.{17}0.0.{32}|
  .{29}1.{24}0.{19}1.{7}|
  .{29}1.{46}1....0|
  .{30}1.{18}1.{9}0.{22}|
  .{30}1.{28}0....1.{17}|
  .{32}0.{25}1.{6}1.{16}|
  .{33}0.{22}1.{12}0.{12}|
  .{33}0.{6}0.{11}0.{29}|
  .{33}1.{5}1.{31}0.{10}|
  .{34}0.{13}0.{8}0.{24}|
  .{34}1...1.{35}0.{7}|
  .{34}1..1.{29}1.{14}|
  .{34}1.{38}01.{7}|
  .{34}1.{5}0.{40}1|
  .{34}1.{6}1.{38}1.|
  .{34}1.{7}0.{31}0.{7}|
  .{34}11...1.{42}|
  .{35}0.{19}0..0.{23}|
  .{35}1.{12}1.{24}0.{8}|
  .{36}0.{6}1.{17}1.{20}|
  .{36}0.{7}1.{17}1.{19}|
  .{36}0.{8}0.{13}1.{22}|
  .{36}1.{14}0.{9}1.{20}|
  .{37}0.{26}1.{16}0|
  .{37}1.{27}0.{10}0.{5}|
  .{38}1.{21}1.{7}1.{13}|
  .{39}0..0.{20}0.{18}|
  .{39}0.{15}0.{19}1.{6}|
  .{40}0....0.{28}1.{7}|
  .{40}0.{15}1.0.{23}|
  .{40}0.{5}1.{16}0.{18}|
  .{40}0.{8}1.{29}1..|
  .{40}00.0.{38}|
  .{41}0.0.{20}0.{17}|
  .{41}00.{32}0.{6}|
  .{41}1.{16}1.{21}1.|
  .{41}1.{8}1.{18}0.{12}|
  .{42}1.{31}1.{6}1|
  .{42}11.{27}0.{10}|
  .{43}0.{34}10..|
  .{44}1.0.{10}1.{24}|
  .{45}0.{9}0.{5}0.{20}|
  .{45}1.{12}0.{22}1|
  .{45}1.{17}1....0.{13}|
  .{45}1.{9}0...0.{22}|
  .{46}0.{11}1.{19}1...|
  .{46}1.{24}0.{5}0....|
  .{47}11.{8}1.{24}|
  .{48}0.{12}1....0.{15}|
  .{48}0.{15}0.{13}1...|
  .{48}1...0.{13}0.{15}|
  .{48}1.{11}0..0.{18}|
  .{48}11.{21}0.{10}|
  .{49}1.{7}1.{14}0.{9}|
  .{51}1.{12}1.{5}1.{11}|
  .{54}0.{13}0.{6}1.{6}|
  .{54}1.{11}1.1.{13}|
  .{56}0.{16}0..1.{5}|
  .{56}1.{11}0.{6}0.{6}|
  .{58}1....1.{6}0.{11}|
  .{5}0.{17}0.{42}0.{15}|
  .{5}0.{23}1.{26}1.{25}|
  .{5}0.{34}1.{22}0.{18}|
  .{5}0.{6}1.{13}1.{55}|
  .{5}1.{12}0.{31}1.{31}|
  .{5}1.{16}0.{39}1.{19}|
  .{5}1.{16}1.1.{57}|
  .{5}1.{24}1.{15}1.{35}|
  .{5}1.{24}1.{47}1...|
  .{66}0.0.{5}1.{7}|
  .{6}0....1.{24}0.{45}|
  .{6}0.{19}0.{7}1.{47}|
  .{6}0.{23}0.{14}0.{36}|
  .{6}0.{25}1.{41}0.{7}|
  .{6}0.{46}1.{22}0.{5}|
  .{6}0.{52}11.{21}|
  .{6}1.{35}10.{38}|
  .{7}0.{20}0.{16}0.{36}|
  .{7}0.{34}1.{20}1.{18}|
  .{7}0.{6}0.{36}0.{30}|
  .{7}0.{7}0.{15}0.{50}|
  .{7}0.{8}1.{42}1.{22}|
  .{7}1.{5}1.{56}1.{11}|
  .{7}1.{67}0..1...|
  .{8}0.{10}0.{38}0.{23}|
  .{8}0.{41}11.{30}|
  .{8}0.{9}1.{37}1.{25}|
  .{8}1.{50}1.{14}1.{7}|
  .{9}0..1.{55}0.{13}|
  .{9}0.{21}1.{42}0.{7}|
  .{9}0.{59}00.{11}|
  .{9}0.{9}0....1.{57}|
  .{9}00.{41}1.{29}|
  .{9}1....0.{20}0.{46}|
  .{9}1...0.{41}1.{26}|
  .{9}1.{30}0.{16}1.{24}|
  .{9}1.{30}0.{37}1...|
  .{9}1.{30}1.{14}1.{26}|
  .{9}1.{40}01.{30}|
  0.{17}1.{34}0.{28}|
  0.{23}1.{43}1.{13}|
  0.{30}1.{26}1.{23}|
  1.{13}00.{66}|
  1.{28}0.{42}1.{9}|
  1.{36}0.{35}1.{8}|
  1.{42}1.{32}1.{5}|
  1.{49}0.{16}0.{14}|
  1.{52}0.{7}0.{20}|
)$

Tested on Regex101.

 The regex is looking for an 82-character string S of 0s and 1s. It
 performs a large number checks of the form (after applying de
 Morgan's) S[index1] != digit1 OR S[index2] != digit2 OR S[index3] != digit3,
 which make up the 3-SAT clauses. The regex size is
 linear in the number of clues, and logarithmic in the
 number of characters in the key (due to the .{n} notation).
 Unfortunately though, to be secure the number of clues has to go up
 with the size of the key, and while it's certainly possible to make an
 uncrackable key this way, it would end up being quite a long regex.

Match: x. Non-match: 0011001101000000000111010001101101011000010011011010000000010001011111000100010000

Match: aaaabaaacaaadaaa. Non-match: 011100110010001010111101001010010011110010011010110101010001101100101111111111 + 0000. Just a few seconds slower...

Wow that was fast - did you guys brute force it?

@Sp3000 I did it almost manually... Surprisingly the statistic method worked.

@Sp3000: I would've bruteforced it but that was no fun. Instead I converted your sequence to a 3SAT and cracked it with minisat. Took 0.3 seconds (time spent converting, ~10 minutes)

@nneonneo Technically, your key isn't valid because both strings have to be between 16 and 256 characters (inclusive). But finding a match to this one is obviously trivial, so I'll give you this one, because you've cracked the hard part (and I hope user23013 won't mind, because it's not putting him in danger of losing his robbers' trophy). ;)

.NET flavour, 141 bytes [cracked]
(?=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))^.*$(?<=(?<![][])(?(c)(?!))((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!))(?![][]))

Another one for the robbers! I'm sure this will be cracked, but I hope the person cracking it will learn something interesting about the .NET flavour in the process.
Tested on RegexStorm and RegexHero.

 I figured this one would be interesting because it relies on the interplay of all three landmark regex features that you can only find in .NET: variable-length lookbehinds, balancing groups, and right-to-left matching.
 Before we start into the .NET-specifics, let's clear up a simple thing about character classes. Character classes can't be empty, so if one starts with a ], that is actually part of the class without needing to be escaped. Likewise, a [ in a character class can unambiguously be treated as a member of the class without escaping. So []] is just the same matching a single \], and [[] is the same as \[ and more importantly [][] is a character class containing both brackets.
 Now let's look at the structure of the regex: (?=somePattern)^.*$(?<=somePattern). So the actual match is really anything (the ^.*$) but we apply one pattern twice, anchoring it to the start once and to the end once.
 Let's look at that pattern: (?<![][]) makes sure that there's no bracket before the pattern. (?![][]) (at the end) makes sure that there's no bracket after pattern. This is fulfilled at the ends of a string or adjacent to any other character.
 This thing, (?(c)(?!)), at the beginning is actually redundant for now, because it only makes sure that the named capturing group c hasn't matched anything. We do need this at the end, so at least it's nice and symmetric. Now the main part of the pattern is this: ((?<c>[[])|(?<-c>[]])){15,}(?(c)(?!)). These groups are called balancing groups, and what they do here is match a string of at least 15 balanced square brackets. There's a lot to say about balancing groups - too much for this post, but I can refer you to a rather comprehensive discussion I posted on StackOverflow a while ago.
 Okay, so what the lookahead does is to ensure that the pattern starts with those balanced square brackets - and that there are no further square brackets next to that.
 Now the lookbehind at the end contains exactly the same pattern. So shouldn't this be redundant? Shouldn't something like [][][][][][][][] fulfil both lookarounds and cause the pattern to match?
 No. Because here is where it gets tricky. Although undocumented, .NET lookbehinds are matched from right to left. This is why .NET is the only flavour that supports variable-length lookbehinds. Usually you don't notice this because the order of matching is irrelevant. But in this particular case, it means that the opening square brackets must now come to the right of the closing square brackets. So the lookbehind actually checks for anti-matching square brackets, as in ][][][ or ]]][[[. That's why I also need the check (?(c)(?!)) at the beginning of the pattern, because that's now the end of match.
 So we want 15 (or 16) matching brackets at the beginning of the string and 15 (or 16) anti-matching brackets at the end of the string. But those two can't be connected due to the (?![][]) lookarounds. So what do we do? We take a matching string and an anti-matching string and join them with an arbitrary character, giving for instance [][][][][[[[]]]]!][][][][]]]][[[[.
 I guess that leaves one question... how on earth did I figure out that lookbehinds match from right to left? Well I tried some arcane regex magic once and couldn't figure out why my lookbehind wouldn't work. So I asked the friendly Q&A site next door. Now I'm really happy about this feature, because it makes balancing groups even more powerful if you know how to use them right. :)

Match: [][][][][][][][]a][][][][][][][][. Non-match: That's interesting...

@user23013 Yup! That was quick. Were you already familiar with those quirks of .NET? :)

Wish I'd figured out the lookbehind quirk 5 mins earlier

No. But I already know quantifiers are not allowed in lookbehind in PCRE. I think actually looking backward is much better than that.

@MartinBüttner So, to confirm, lookbehinds actually match from back to front?

@TwiNight Yes, I'll add an explanation later. .NET actually has an option with which you can match the entire expression right-to-left. It's just stated nowhere explicitly (but proven empirically) that the same technique is used to implement their variable-length lookbehinds. Here is the SO question where I originally stumbled upon it myself: http://stackoverflow.com/questions/13389560/balancing-groups-in-variable-length-lookbehind

Python flavour (200127 bytes) [cracked]
Just so that we may (hopefully) see something last a day, it's time to bring out the big guns :)
The problem with 3-SAT and Hamiltonian path is that the complexity is in terms of the key size. This time I've chosen something which is dependent on the regex, rather than the key.
Here it is: regex. You might also find this file useful. (Don't worry, I haven't hidden anything weird in there this time ;) )
I used RegexPlanet to test this one - it was tough finding something that wouldn't time out :/. To check if there was a match, see if your string appears under findall().
Good luck!

 The regex is just "find a string of length 64 which appears as a common subsequence in a set of 20 strings of length 5000". There were too many solutions though, probably.

Match: d,mE~JZ0,_:3kBdLdgBSzJ!@MLrrAgKsf@Pl35N9bxsIf@ReVU>:YDg`d1MjL@_-. Non-match: { line|fold -w1 >filea; while line >filec; do fold -w1 <filec >fileb; diff -d --old-line-format= --new-line-format= --unchanged-line-format=%L filea fileb >filec;mv filec filea;done;cat filea;} <file1|tr -d $'\n'|head -c64;echo

Ahaha I'm beat - I guess the sequences were too long and there were too many solutions

@user23013 That sounds like a lot, but it's actually not too bad, seeing that there are 5437589409196755010929519821645784067024309122301926366910354757626905801389085035074667925844349168139762829668081680641 different strings of length 64 with the available 77 characters.

Well, I'm wrong. There are not only 718406958841 solutions. And my script has a bug so it ignored the last pattern. But the common subsequence of the first 19 patterns happened to be also a subsequence of the last one

@MartinBüttner I mean I don't know exactly how many solutions there are, and that number is wrong. Their longest common subsequence has 718406958841 (corrected value: 97082021465) subsequences of length 64. But there are other CS's which are not subsequences of LCS.

@user23013 To double check - did you find the common subsequences pairwise? If so then the sequence length was far too long :/

@Sp3000 I find the LCS of one string and the LCS of all previous strings.

Python, 145475 bytes [cracked]
Thanks to the Wumpus for teaching me the importance of checking our indices :)
Same deal as last solution, only hopefully not broken this time. Raw regex: http://pastebin.com/MReS2R1k
EDIT: It wasn't broken, but apparently it was still too easy. At least it wasn't solved "instantly" ;)

Non-match: 1040060321170122554027333022674205250442151362365165773421664173556667110413375720720711725045122733213710556062114131057357354554245723416516004761215632214223735570625116160162051407026445600345370604702671021412723536217011007021752560474402200436670402 Match: minisat2hoursCPU

Ayup. You got me. That was pretty quick. Maybe I do have to bust out my 1GB regex after all...

Java Pattern/Oracle implementation (75 chars/150 bytes UTF-16) [cracked]
(Code name: Bad Coffee 101)
This is the Pattern object, with CANON_EQ flag, to be used with matches() (implied anchor):
Pattern.compile("(\\Q\u1EBF\\\\E)?+[\\w&&[\\p{L1}]\\p{Z}]+|\\1[\uD835\uDC00-\uD835\uDC33]{1927027271663633,2254527117918231}", Pattern.CANON_EQ)

Test your key here on ideone
There is guaranteed to be a key. Read the spoiler if you want some confirmation.

 As you can see, it is not a normal regex. However, it runs without Exception on Oracle's Java version 1.6.0u37 and Java version 1.7.0u11, and it should also run for the most current version at the time of writing.

This makes use of 4 bugs: CANON_EQ, captured text retention of failed attempt, lost character class and quantifier overflow.

Match: "(?:e\u0302\u0301\\|\u00ea\u0301\\|\u1ebf\\|\u00ea\\\u0301|e\u0302\\\u0301|\u00ea\\\u0301|\u00ea\u0301\\|\u1ebf\\|e\\\u0302\u0301)\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00\uD835\uDC00" (quoted form). Non-match: JavaRegexSoBuggy. ideone for match: http://ideone.com/DEesdk

Bugs found: (1) CANON_EQ expands precomposed characters into alternations internally, which breaks hilariously inside \Q\E; (2) repetition lengths are truncated to 32 bits; (3) there's some weird thing going on with the character class matcher that causes it to skip the alternation (didn't quite figure out what the bug was exactly).

@nneonneo: Your explanation is correct. But you forgot the backref \1 bug. And yes, there is a bug in the character class. How did you figure all this out in less than 2 hours?

I started working on it 20 minutes ago. You made it pretty obvious which parts of the problem stressed which bugs (because each bug was basically in its own group), so I figured out how to satisfy each part independently, and then combined them. I got lucky that I didn't have to actually work out what the character class was doing. (I also got very lucky that Java spits out the "expanded" internal pattern when you have a syntax error :)

Also! I don't believe that the captured text retention is necessarily a bug. That seems to be how the possessive quantifiers work. (It's also a rather useful property for certain regex hacks...hm...)

@nneonneo: The lost character class necessarily makes the first branch fails. The second branch continues from the content of the capturing group in the first branch, which should not be valid in other flavors.

Good to know. Thanks for the challenge, it was fun finding out how buggy Java's regexes are in the corners ;)

.NET flavor, 17,372 bytes [cracked]
This is still an easy version. It needs more optimization to work with longer strings.
xz base64:
/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4EPbB2hdAC8KA+QKYhePb5XYF74CIWXzFZa9NcIQEk3v
/V2BJ4+pWDeuHyJglyhWD3Jp454EQmzShYGwtV0HYNg/uM7nyzGoXBbC//+zrYYUFKzVPHOpsGOG
dHt5rN7ffwyFyGP7scto6uWZ3Tlf+Udsikqx8XmtBTZxs+eKVsjWcBWYs+v27AW4AIesr2/aArhe
hagu80JX4+EYSYLfj6hqDPXA3XT9pUJLw+KESRPk+cOH0IrGx/PhNJxlv/Oq2FF3sCwq5GzIrhq2
FsOqyX4hE73pT4RI4sbY+hOveol93r3n1UZKX7/+gR3/EvS86lvgzZId0ktKQ4bZdPmlFVUB5aSM
xHPQ9KhkHAa1mxT3YhTs+CMased0tdTBeN+r/wzGzikIvCzYL0fb9YfdLt7kviJY4FC5PgS46UqY
IOpXcixcxHdznxoXf463nnUBl9p6bHyCBZSKzRLt9Tca859POZWLK3aBnBMEKve66Z/Wq08VdW3i
7XABm6Bp98O+xThLqjY3ZeiOiuUSFBOp4bXaJwW1ibgk84eVN/LUvYc+13SHEjz957RLNqzIccHT
a4Uz91v36AkbUgIzT9IaRg8OVmMR6FgFk/szxATDEKAjOGp6ugavV2UNNFQzXEklkidM0VSsKVyW
9mEwktk3msx3SUV0Wgi4ErsnQVVOE9zgHeLeYBvsXcdeOG2qFUX1u3GrUW6Q6/9cuypfOJNvrC4l
/DO0Lt/8uU1Fcs2ndF1akVS6jlYrsmTUV7Nr99BtKOv23OB8YVekWYRQWI9vEG+/4dyqK8+o5Xpl
oxgALMkQ78jWzYkT11xIemZBN8Vqj3AEla28gVteFDR11t5rug3XHkklcHq5CUQHsiB8IryWZDI7
mTdopip2ewbK92DaHNXc4rSvpcNcdNjjX9cbt0RfC3FINvw8LCMjZd3bOEc8gKWjJJUtphh7NN5p
0BIKScGcytglHzVAF3SX+MLQ4ZoOY0MK55cNb2lIi9FmYkoVZpRBA3bTG5+ts8ZdmiQRktwM5CMS
vQg8WtB5xjD7ii1G3LZ2OAKHvHix+ceia9wJQ/kYUg8xhbo8mbc3MiFMgv5lBcLbxESeOE1NATLS
+Y2R9m6l0VNl2MNjNejIKFF2X0j0I4+xA3xJd31rMpKT7stUBJ4ADmv4W16a6RQH/pAWi1U3jCdk
6p01MvfJ+FKbAlSquKuiJ3vi+nPPUXTCfWxnfOShMmgECCJTp9yzvKa6PFT1UDbeD63uPUpK9Syy
Z+KkdmhE4ieL8Ksm7ExwR+26FNC5M/Vq2LHJYSb7jcG6PgZiBncbUQv0hdV4XuC00E/6k7mOFx10
B09NuY7MWntHJXFagjdUUXUru2Fhssyf7hHXTj+9VcdWSlQimSJB1CIG4UK5qsLfqkrcHBEoiAUO
ZNAMwIez4C1C75paivtTHfO4u8oDSLPV9UPcvUlpTN31QY/PL7m6p38yOuc91vrCGjC5ZP2FKgv3
O3DEgV+uZuNQNVe4EvrNP2+LdlC2GrsNZ+0HlgPatW2FJP29awdhrt999q2o63yA2FgItq6EKqhO
55iqek4WDViZKEppGIsKY/I/pUmDrOnr5tmSVjOJur0H1YTC8P9rW54vrOkpvNFnfT1tcC0uOZ44
SiPCAEgV/dFEzF4LsBPovyDyu6PALd3RpzLX0+ETIUI1BSE6hspXaY4J2ti8FhkpG3faTD0yoY5+
dzbnsS+u+7Nf7pJTjHQe7q1iMf3bXZwMcc8vX3iabaLxVI9j/skwzijb5XPBSr95jxjj++LOx1ak
XWIyAHpQJlPtFbTFmhmS39sFEqEMGgjTaYZje1kRdNX6RvTZ/5WQLM0Y5/5qRTm5WswdLoh13OQ7
t+T1vAWvf0y3L82OQfFLJl/Apq1vRGaBLC8GYpXUpHScN8uDCsC8P/OTdqE6/bpvhEdIY/BCPjYR
jLGIzJcG9rkza8ehyVfFofet66u+1Rq7BGC0h8anVGvTAs2Hji+OccDju+GVFJ9fenrcqumDTvvx
zw0q9QoZZgjv8sU8421xNF5MXD8U2f1/rUYPd3eZBjKRkRGdV6Z9vOi0itVtkEhjhM9VG+vlPA6G
204tNGfEG0dhZJPT88fTUS1k1U1qz8lXjMi9W8Sb7NOEBUtWO3T38XTshEU6oFqyGSPzjW/E9ZGF
MYTQ5IYJcNPNW2qujI1eQcHChiCAWqBPz06/7+YJLV/5+XUqIWsV8FJPXMaGYVquN4O0RF9cq8fN
S1M5nCiFXcvYPgM9GQkUrKHUx7/h+r9LXT/jCainyDya4Bep2d6qw7MSs6Nz5TNKfXuQatPOQFKp
zxZWKpmLfBi25rioNUuSz80L0/Tp08JbixcnwkYcyywSs1+DpiBhvW/HjCOn4vUQ5eLbwFARLb9k
8ekQJecNe7GwJj8zqbsLmwMQG8BRWiUhWwvR3jW+uxNVBprkI+ngng252klBQOO1KB7lPuh7MiIe
rfUv5Al2+tep3mgGPq6wuU+e/D5uE8BwM57AQSXiSShipvBs5ya34zTYZhmiAAD/eeasymtkVgAB
hA/chwEApy/HVbHEZ/sCAAAAAARZWg==

Ungolfed:
/Td6WFoAAATm1rRGAgAhARYAAAB0L+Wj4FTrB+NdAC8CgQKxGND7urrBgy10a+lq9gP9wSLgMqJb
pNHJMhYOiDHCSukpsHuQPqPd/4L4ZTIqW7+CNF2+iSlEPkpGKx8mgtz/0/0uh1K/PjpgF6CKpTao
OagiH/R/0k1JSdZny4EGQRhgjeEqcHSYN0XwYUNQ4hNcNnG9oNx89YRd+fhb0McwGItppBEJP5ly
fV0fuxawst8IqkzqRrzX3wTC1Pva//ko4PZHtZaD231oqRJeK8ed6VBqhYMUn/VakiYh9PmdVJ4N
DzDTLQz/p1pH2R3zpDsOPwjWU4zPHiqq/JNgTIzvlYwhBpjB/mxI+VqFhH+5vCWo0iei6zDvQUOp
5jFgukLYRlKrqLPG4eMLq0mfyybUyLLPV9+MrPgX/GUmewiH+VprnnLBWybIsZwq+j+dCzC0zB8I
fWKTjv6RpT7kJiIt5d5RRnoLOv2tusA5VvIpKWAhyNB7/kp2udTWJ0AH7fcbfxo/xWndV6umQK8s
efzG+KIlZyIDDa/Rnpc3avNgxVZnop1A1ZEWSvDsuRslkBkIhSpqoGh4zoAWrZjbOrOSBSS90w14
CC2t/CIrXlJJ4WyjWyh+N4RHDWCM1sCX/WFf+elMvIjxYe5cGZdWoeXmNfTYRXfhTzSNQRAhYcq5
SbpDahvq70vttfQ0lMdxtvy2IDZzJZMQgo9s0dhp+TG4zc7DK47RuPpPZffz8cKGvXGUVCvGugug
jvB9jehPbMH8UfNAiSlvQJGYU5F7POvvAoYbDcqUJGYe456+r066D5lFtsjqm8R5jMa9P3P4PMfp
VNHyYCDa7ddcwJz9umgAHjmMXMEXqwl0RLEHzug43lsl/ecvt+FdMZnlnch/3S7l7xt/uSNnYzgv
h9nP0nTuoTP6gpQy3/Gbegnbd9xFaXrUletx1mG3uKB7MBsyHGQAcldlDenw7EcE2F3zeEBOEOiZ
yniQp6cvQs34TEFIoS3y7E/34YaJ/A2GoXkW0U1wqpy9Q1wWS1yaPuUZsEoPXmt8vk/pMDTY7e8H
wh6JaoHpZ38fCc+ZT4USaQ+vG3Magsu1hEm+lYw9s9ZTU50jva1g8TmrCyJvPSkeZS1pc/UaDWpQ
mcgeQp0Gcwhgx7qW+d7JVp2YvtyoODGc9mSaypL4z3MegZu6f6p9h7cGxg3SPQrZ3HqZyiszuzsh
PPRXGM89GDrvIKbzWMx2AFSB38Jq4SdJsu9qgQ8XeYMlawRWatLPCyn8VR/kY9Bndj0M81wGr6Tm
vMtj50/Lo4efc/qhqio8NahizZtoy3gOBtYEzBcTQ3vX9CdMRP4VHDtm1mvTeGbwgFLa6HRFF7m+
YpQb2oUjdFkOc6Ntaj8xkpdVZr9HtUUwE4xZNtaGE1DawFLe4EtkQ5qoJ0RTXgLncrejbXIKc7N4
Sqk9fz/hhPczd6jJLomdiEzneIekW+Fkh/E0vh6YSnempM7fVmUsh795rASSm1OcKWLHlVKoJEIx
F5Rh33WixS39tFe8SpXn8/NAuxrG8sHrzFfaTdOVG0yIn16E00CfbWjXlNIEVIEzL8flQnVVcUiR
XrzjFnFqoZi39jowpAXHTYVa6b6HWMIrgQ0bnqwwvKrcBqJJ+AWf7DFwES/CQmTq8kLSoBwZmZ3x
Ruw4FgK5Kah1dUX2SP1z2tLFpUrZdwRRS5KragvS1rCPUOxoKjyRPC5zRGam9jZQpxSHIm1A/PU2
Iye9CqC0nvoBZumMNpGhkWd905SUdRaKGXaZ9B4/IyFu+J2s+Gwyfsiaw3EXetS0gWcpA4IN3G13
8MqzxGg8d9o0yKK9QpfTNzXVQjikiT+8tR1bYp9BLBJkoralecy2vKNr5uJFKU7UgbMxq4Mj13WA
v5qRjTKg04KtQCSGcPv6vanYfq2/Kjyiv145NNR9tDzoJSqTd9fujxOOY/aitPzSnO0Zz1iz0SQD
jixBBsfFIOhrczlRCuBSD0Eu8uG8ZvSbpjMb0BEpxTEmFGCm9WHaxhwtA7fRO8mGCSFSooxPcZrx
ThMA+9A5Zetnuo5+S74tMciJAHfZA7a6k6PP10JBP9OmcegXm/7gLUgklW2nerK+Sv5rBRuMdazE
f8h/Oh94uSTdCffdjrl3poMI/FpktngiM5vEOTvoUeJd8R25nEso9kuGJchO6DrPe03/UStAaWf2
Mpi5/ShBST8H2EpdVVzTCkHW1R/JL/YSGdJpBwiYtizNu4SfnaqUQN2dCZzAmuYofJ+gnQMR5xuG
GwDKDpjN8T7SdO/KAxMD1/1DVfAhZYbqtBaU70jbGC+6cl9XPGV3B0VfJDXKPKhDD9rWWfL4L/+0
7UsGl3kAp4nBokcF23RBQVA+f6iKlF1edQQq6OSsX+oiZlG2BghXbO0iIMIkK3Awl5Os1jmHalfS
R5G3bTIXEmYf+pQ8W0qY1i17XqailA3E3tngshbv2ffw6uYBmETgcYD4p3UOI/8gU6vLZ1AbsXdd
V0w7bBoGnc3KBQG9jm7PxVFeQ6hZY5z7cDUtytLA4SBCfUYvv7rN+7ctMbBQPO2dlT1lm7uoN5HK
JeWyFaNaWtbOA5blNwjBDH9QSxZsEjIY7FENQxW6U5dQQuPctw2EUMT9DC2M1ff3aFtbaqoK5HcI
9VeDSeBxFq1jXwOycVnNtWbMGufP3KtbJegpF1qvlDluuzY0jtJHz16hkOiFi7HcnK798ZBNWwAA
zJ7uOgG/vd8AAf8P7KkBAO5B2vaxxGf7AgAAAAAEWVo=

Tested on RegexStorm and this blog and RegExLib (with all options unchecked).

 The solution to this regex is the factorization of 5122188685368916735780446744735847888756487271329 = 2147852126374329492975359 * 2384795779221263457172831, with the result encoded in base 289, least significant first.

 Each digit is firstly split into two base 17 numbers to make the calculations faster. This is also how the product is encoded in the regex.

 Each pair of digits in the two numbers is then multiplied into capture group a0 to a38. Each of them is a digit of the product. The current position is kept track by p and q. And the carry is processed after the multiplication, while comparing the product.

 It is in base 289 because it was designed to accept two 1024 bit numbers, which has 128 base 256 digits each, and I didn't think of removing the comma so the full string with base 256 would be 257 characters.

The 1536 bit version is here. It accepts two 768 bit numbers. The numbers in this easy version each has only 81 bits.

Match: Ľê¯6Aĝ4aþĀ,lŃŝĿBİŢŞĩï (escaped: \u013d\xea\xaf6A\u011d4a\xfe\u0100,l\u0143\u015d\u013fB\u0130\u0162\u015e\u0129\xef). Non-match: VeryNiceMultiplier

ECMAScript flavour, 30 bytes [cracked]
^((?![\t- ]|[^\s])(.)(?!\2))+$

Here is a rather simple one for the robbers to crack. It's conceptually not too hard, but might require a little research (or scripting). I don't intend to list myself in the leaderboard, but if someone cracks it within 72 hours, this will count towards their robber's score.
Tested on Regex101 and RegExr using Chrome.
Well, that was quick!

 The regex was supposed to match any string consisting of distinct non-ASCII whitespace characters. However, I forgot a .* before the \2, so it actually matches any string of non-ASCII whitespace, that doesn't contain two consecutive identical characters. There are 18 such characters in the Unicode range up to code point 0xFFFF. The match posted by user23013 is one such string, consisting of 16 characters.

Match (base64): wqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBn8Kg4oGfwqDigZ/CoOKBnw==, Non-match: aaaabaaacaaadaaa

It is not distinct but only alternating, with only two distinct characters.

@user23013 Damn, I forgot a .* in the lookahead. Good catch. Should have tested more thoroughly.

Ruby-flavored, 24 bytes [cracked]
^(?!.*(.+)\1)([\[\\\]]){256}$

Please include a link to a tester where your intended key is working (like http://rubular.com/). (Also, obfuscation/golfing pro tip: if you use PCRE instead, the character class could be written as []\\[] ;))

Link added. I suspect Wumpus has cracked it, could prove it with a permalink to rubular.com

Non-match: soylentgreenispeople. Match available at http://www.rubular.com/r/TCqjcaGsU1 not posted here because of how the comment system handles long words.

@WumpusQ.Wumbley Great! If you include the non-match into that same comment, we can clean up all the mess above this.

PCRE (1043 bytes) [cracked]
After randomly generated regexes have failed me (the ideas were good, but I couldn't generate adequate problem instances), I've decided to hand craft this one. I dub it "A whole lot of rules to satisfy".
^(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)(?!^\(.*)(?!.*\(.{250}\).*)(?=.*\[.{250}\].*)(?=.*\{.{250}\}.*)(?=.*\[.\(\).\{\}.\].*)(?=.*\}...\[...\[...\]...\]...\{.*)(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)(?=.*\[\{\{\[\(\{.*)(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)(?!.*\(\{\(\(.*)(?!.*\(\)\[\].*)(?=(.*?\].*?\)){15,}.*)(?=(.*\[.*\(.*\{){5,9}.*)(?=.*\({3}.{105}\[{3}.{105}[^}{].*)(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)(?!.*\(\(.{178}\])(?=(.*\[..\]){8,10}.*)(?!(.*\([^\(\)]{5}\(){4,}.*).{63}(.{6}).{130}\11.{51}$

And expanded:
^
(?=^([^)(]*\(((?>[^)(]+)|(?1))*\)[^)(]*)*$)
(?=^([^][]*\[((?>[^][]+)|(?3))*\][^][]*)*$)
(?=^([^}{]*\{((?>[^}{]+)|(?5))*\}[^}{]*)*$)
(?!^\(.*)
(?!.*\(.{250}\).*)
(?=.*\[.{250}\].*)
(?=.*\{.{250}\}.*)
(?=.*\[.\(\).\{\}.\].*)
(?=.*\}...\[...\[...\]...\]...\{.*)
(?=.*\(\(..\(\(.{68}\(\(\)\).{43}\)\)\)\).*)
(?=.*\{..\{..\{.{65}\{\}\{\}.{33}\{\}.{107}\}\}.\}.*)
(?=.*\[\{\{\[\(\{.*)
(?=.*\[\[..\[.{6}\[.{6}\]\]...\]\].{6}\[..\]..\[\].*)
(?=.*\]\]\}\}\}.\)\)\)\).{96}\]\}\}\]\]\]\}\]\]\].\)\]\].*)
(?=.*\]..\).{6}\(.{7}\{.{5}\[...\[.{5}\{\[.*)
(?=.*\[.{87}\{.{45}}{.{38}}.{27}\].*)
(?=.*\(\{.{32}\(.{20}\{.{47}\].{43}\{\{.{25}\}\}.{18}\].{5}\}....\}.{5}\).*)
(?=.*\{.{12}\(.{5}\(...\(...\{\[.\{\[\[.*)
(?=.*\{\(.{21}\).{8}\}.{14}\[.{7}\]..\{.{5}\{\}....\}.*)
(?=.*\(.\{.{49}\{.{16}\}.{25}\}.{66}\).*)
(?!.*\(\{\(\(.*)
(?!.*\(\)\[\].*)
(?=(.*?\].*?\)){15,}.*)
(?=(.*\[.*\(.*\{){5,9}.*)
(?=.*\({3}.{105}\[{3}.{105}[^}{].*)
(?=.*\(..\).{5}\(\)....\}\}\].\{\{\[.{22}\[.{35}\}\}\].*)
(?!.*\(\(.{178}\])
(?=(.*\[..\]){8,10}.*)
(?!(.*\([^\(\)]{5}\(){4,}.*)
.{63}(.{6}).{130}\11.{51}
$

Tested on Regex101 - depending on your computer you may need to up the max execution time.

This regex encodes a whole bunch of rules that just need to be satisfied. Any solution will do, it's just finding one.
The first three core rules require that, separately, all ([{ brackets need to be balanced within the key.
Most expressions require that a certain "shape" needs to be in or not be in the key. For example, the 8th row requires something of the form [.(.).].
Rules like (?=(.*\[.*\(.*\{){5,9}.*), for example, require that [({ alternation happens at least 5 times. Note that this line in particular is bugged on many levels, unintentionally.
The backreference \11 requires one six-character substring to appear twice in particular positions.

Match: [((({.[.[](){{}{].{.(({){(.[]()....}}].{{[[....).[..]()(}..[..]([....(([{((({).](){.{}{}{}....}[[()[}}][{{[({[[[.]]}()]].{}.]{[..]{.[]]}}}())))(())[(.].{[.{[[..[()].()}{{.[...[}{.]..)]...{.])))).}}..([......{.....[.]}[...}.{[.}...}})}.))).]}}]]]}]]].)]]..}. Non-match: WhatANastySetOfRulesYouHave.

I increased the execution time to 50 seconds. By the way, if you just use the proper non-greedy quantifiers in (?=(.*\[.*\(.*\{){5,9}.*), then you won't need to increase the maximum execution time (same result) - the matches will be instant.

@nneonneo Ahaha yeah, I realised that after I posted. Can you post, say, a pastebin link for your key though? SE comments seem to be acting up again

@nneonneo Also if you have so many dots in your solution, clearly I didn't have enough rules :P

Here's a regex101 link with my solution visible: http://regex101.com/r/gP2aX7/1

@nneonneo Nicely done :)

PHP, 168 bytes [cracked by nneonneo]
^((?![!?$]*[^!?$]))?(?:[^!]\2?+(?=(!*)(\\\3?+.(?!\3)))){4}(?(1)|Ha! No one will ever get this one...)|(?!(?1))\Q\1?!($!?)?\E\1?!($!?)?(?<!.{12})\Q(?=(?1))\E(?=(?1))!\?$

Here is a regex demo.
P.S. This game is hard.

Match: \1?!($!?)?!(?=(?1))!?. Non-match: IncrementalRegexTestingWorks

@nneonneo Ah, you're too good ;)

PHP, 395 bytes [cracked by nneonneo]
^( *)( *)( *)(['.-])((?!\4)(?4)+?)((?!\4|\5)(?4)++)\1\3whale
(?=.(.))\6.\7\4(?!\4|\6)([_\/])\3(?!(?11))\8\2(?=\2)\3\1_((?=\4+.).\5(?!\6)\5)(?!.?')\7\4
(?=.\7)\6.([,`])\3{2}(?=.((?!\8)[_\/])\11)\Q(_\E.\4{2}(?!\.)\5((?!\10)(?10)(?!\4+|\5|\6))\1\3{3}(\\)
(\3{3})\13\2{2}\1{1}\3+(?<=\S {10})\4\1\3\|
\1(?=\12)(?12)(?!`,)\10\4(\11{2})\4\14\10\15\9\8
\14{2}(?=\6)['-]\4(?<!-)\11\8\11\4\6\11\15\.-|(?!)

A better jigsaw than my last entry.
Note: The matching key is multiline, with each line separated by the new line character \n. Rebuild some ASCII art!
Here is a regex demo.

Match: 202e272d207768616c650a2d3a3a2e2f202f205f2e27273a2e0a2d3a2c2020285f5f2e2e27602020205c0a2020205c202020202020202020202e207c0a602c2e5f5f2e2020202c5f5f2e27272f0a2020202020202d2e5f2f5f2e2d5f5f5f2e2d (hex-encoded). Non-match: IDon'tThinkIGotTheRightPicture. Proof workspace: http://regex101.com/r/gF9pU0/1

@nneonneo Wow! You solved it :D But the right picture is here: http://regex101.com/r/oM9rC4/1

Yeah, I figured I didn't have enough spaces (but the regex didn't check too strongly). And, it seems I have interchanged .-' at the start to .'-. In hindsight the former is much more plausible for ASCII art ;)

.NET flavor, 53,884 bytes [safe]
Generated by GnuPG! And extracted by pgpdump. It is 1536 bit because longer versions failed on the online tester.
xz base64:
[encoded data, 5884 characters]

Tested on RegExLib (with no options selected). I hope I didn't cause too much trouble to them.
You probably want to crack the easy version first. It is the same as this one, except for having a much shorter key.
You probably also want this number:
1877387013349538768090205114842510626651131723107399383794998450806739516994144298310401108806926034240658300213548103711527384569076779151468208082508190882390076337427064709559437854062111632001332811449146722382069400055588711790985185172254011431483115758796920145490044311800185920322455262251745973830227470485279892907738203417793535991544580378895041359393212505410554875960037474608732567216291143821804979045946285675144158233812053215704503132829164251

The key
Match:
ËòčĵċsïÝ²¤ėGâĥÓŧÿÃiTüū&0EĚĵŒR@bĵ¤¿Ĉ=ķüÙļÞďYaŃīŲĢŪÕďųïyĘŊŢĝĪĘŠćĢmtŠîĽþĽłŶāĨĩģTő!ĺw=aŧïųţĨíœą¸Ëč!,ĵţ¨ŌąŜ7ć<ůū¹"VCæ>õêqKËĖ¡ôÕÂúëdčÜÇĺřGĝ¢ÈòTdĩŤŭi§aćŎŭųä«´3ĚÎ¦îŇĬÒÕ¥ńü½å±ì³Jõ«D>ìYũŉ5öķ@ŪĠďàÂIĭųė!

Non-match:
1111111111111111

The prime numbers:
1332079940234179614521970444786413763737753518438170921866494487346327879385305027126769158207767221820861337268140670862294914465261588406119592761408774455338383491427898155074772832852850476306153369461364785463871635843192956321
1409365126404871907363160248446313781336249368768980464167188493095028723639124224991540391841197901143131758645183823514744033123070116823118973220350307542767897614254042472660258176592286316247065295064507580468562028846326382331

Explanation is in the easy version.
The generator script (in CJam)
'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

"
^
(?=["T",]{"FG+)`"}$)
(?=.{"F`"},)
(?!.*,.*,)
(?:
    (?(X)
        (?<-X>)
        (?(L)(?<-L>)(?<l>)|){16}
    |
        (?:
            "
            [T289,]z
            {[~17md["(?<l>){"\'}]["(?<L>){"@'}]]}%'|*
            "
        )
        (?<X>)
    )
    (?=.*,
        (?:
            (?(Y)
                (?<-Y>)
                (?(R)(?<-R>)(?<r>)|){16}
            |
                (?:
                    "
                    [T289,]z
                    {[~17md["(?<r>){"\'}]["(?<R>){"@'}]]}%'|*
                    "
                )
                (?<Y>)
            )

            (?(l)
                (?<-l>)(?<x>)
                (?(r)(?<-r>)(?<y>)(?<v>)|){16}
                (?(y)(?<-y>)(?<r>)|){16}
            |){16}
            (?(x)(?<-x>)(?<l>)|){16}

            (?(p)(?<-p>)(?<s>)(?<z>)|){"F2*(`"}
            (?(z)(?<-z>)(?<p>)|){"F2*(`"}
            (?(q)(?<-q>)(?<s>)(?<z>)|){"G2*(`"}
            (?(z)(?<-z>)(?<q>)|){"G2*(`"}
            "
            "
            (?(s)
                (?<-s>)
            "FG+(2**
            "
                (?(v)(?<-v>)(?<a"FG+(2*`">)|){256}
            "
            ["
            |
                (?(v)(?<-v>)(?<a"">)|){256}
            )
            "]aFG+(2*,W%m*{~\~@`\}/
            "
            (?(r)(?<-r>)|){16}
            (?<q>)
        ){"G2*`"}
        (?<-q>){"G2*`"}
    )
    (?(l)(?<-l>)|){16}
    (?<p>)
){"F2*`"},

"
[
l~17bW%_,FG+2*\- 0a*+
FG+2*,
]z
{
~:A`:B;:C;
"
(?<-a"B">){"C`"}
(?(a"B")(?<-a"B">){17}(?<a"A)`">)|){4100}
(?(a"B")(?!)|)"
}/

]:+N9c+S+-

Input should be the above number.
After you are done, the solution can be generated by this program:
'~),'!i>"+.()?*\\[]{|}^$/,^-:#"-
'ǝ,'¡i>173c-+289<:T;

95:F;
95:G;

{
r~289bW%_,FG:F;\- 0a*+
{T=}%
}2*',\

Input should be two integers.

Too bad. RegExLib is down. I think people should better use a Silverlight or local tester. But I can't test them.

IIRc, RegexHero is a .NET tester in browser, using Silverlight.

Another idea about big integers is to calculate the product mod prime numbers near 200. It should be faster. But the code would be much longer and I'm not going to do that in integer factorization answers.

Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked.

.NET flavour (7563 bytes) [cracked]
Inspired by @user23013's idea
^(?:(?=1(?<1>){5632})|(?=0)).(?:(?=1(?<1>){79361})|(?=0)).(?:(?=1(?<1>){188421})|(?=0)).(?:(?=1(?<1>){164870})|(?=0)).(?:(?=1(?<1>){63496})|(?=0)).(?:(?=1(?<1>){116233})|(?=0)).(?:(?=1(?<1>){112138})|(?=0)).(?:(?=1(?<1>){47447})|(?=0)).(?:(?=1(?<1>){85005})|(?=0)).(?:(?=1(?<1>){17936})|(?=0)).(?:(?=1(?<1>){108053})|(?=0)).(?:(?=1(?<1>){88599})|(?=0)).(?:(?=1(?<1>){91672})|(?=0)).(?:(?=1(?<1>){178716})|(?=0)).(?:(?=1(?<1>){199710})|(?=0)).(?:(?=1(?<1>){166661})|(?=0)).(?:(?=1(?<1>){190496})|(?=0)).(?:(?=1(?<1>){184494})|(?=0)).(?:(?=1(?<1>){199203})|(?=0)).(?:(?=1(?<1>){116778})|(?=0)).(?:(?=1(?<1>){78891})|(?=0)).(?:(?=1(?<1>){192556})|(?=0)).(?:(?=1(?<1>){24995})|(?=0)).(?:(?=1(?<1>){1071})|(?=0)).(?:(?=1(?<1>){192561})|(?=0)).(?:(?=1(?<1>){108082})|(?=0)).(?:(?=1(?<1>){1593})|(?=0)).(?:(?=1(?<1>){26967})|(?=0)).(?:(?=1(?<1>){197983})|(?=0)).(?:(?=1(?<1>){97034})|(?=0)).(?:(?=1(?<1>){86965})|(?=0)).(?:(?=1(?<1>){60480})|(?=0)).(?:(?=1(?<1>){149571})|(?=0)).(?:(?=1(?<1>){100932})|(?=0)).(?:(?=1(?<1>){40519})|(?=0)).(?:(?=1(?<1>){173492})|(?=0)).(?:(?=1(?<1>){80972})|(?=0)).(?:(?=1(?<1>){115790})|(?=0)).(?:(?=1(?<1>){29265})|(?=0)).(?:(?=1(?<1>){91730})|(?=0)).(?:(?=1(?<1>){173140})|(?=0)).(?:(?=1(?<1>){52821})|(?=0)).(?:(?=1(?<1>){176726})|(?=0)).(?:(?=1(?<1>){170211})|(?=0)).(?:(?=1(?<1>){150105})|(?=0)).(?:(?=1(?<1>){23131})|(?=0)).(?:(?=1(?<1>){81503})|(?=0)).(?:(?=1(?<1>){77412})|(?=0)).(?:(?=1(?<1>){106086})|(?=0)).(?:(?=1(?<1>){4284})|(?=0)).(?:(?=1(?<1>){142610})|(?=0)).(?:(?=1(?<1>){167534})|(?=0)).(?:(?=1(?<1>){190577})|(?=0)).(?:(?=1(?<1>){147731})|(?=0)).(?:(?=1(?<1>){133748})|(?=0)).(?:(?=1(?<1>){194750})|(?=0)).(?:(?=1(?<1>){49257})|(?=0)).(?:(?=1(?<1>){49274})|(?=0)).(?:(?=1(?<1>){120767})|(?=0)).(?:(?=1(?<1>){172668})|(?=0)).(?:(?=1(?<1>){24703})|(?=0)).(?:(?=1(?<1>){108160})|(?=0)).(?:(?=1(?<1>){60546})|(?=0)).(?:(?=1(?<1>){56963})|(?=0)).(?:(?=1(?<1>){30340})|(?=0)).(?:(?=1(?<1>){95368})|(?=0)).(?:(?=1(?<1>){59530})|(?=0)).(?:(?=1(?<1>){53388})|(?=0)).(?:(?=1(?<1>){14477})|(?=0)).(?:(?=1(?<1>){28302})|(?=0)).(?:(?=1(?<1>){182927})|(?=0)).(?:(?=1(?<1>){59024})|(?=0)).(?:(?=1(?<1>){146200})|(?=0)).(?:(?=1(?<1>){153746})|(?=0)).(?:(?=1(?<1>){39571})|(?=0)).(?:(?=1(?<1>){134293})|(?=0)).(?:(?=1(?<1>){158362})|(?=0)).(?:(?=1(?<1>){170139})|(?=0)).(?:(?=1(?<1>){182940})|(?=0)).(?:(?=1(?<1>){7327})|(?=0)).(?:(?=1(?<1>){143525})|(?=0)).(?:(?=1(?<1>){119464})|(?=0)).(?:(?=1(?<1>){82090})|(?=0)).(?:(?=1(?<1>){170667})|(?=0)).(?:(?=1(?<1>){49522})|(?=0)).(?:(?=1(?<1>){69806})|(?=0)).(?:(?=1(?<1>){15535})|(?=0)).(?:(?=1(?<1>){16049})|(?=0)).(?:(?=1(?<1>){163358})|(?=0)).(?:(?=1(?<1>){181876})|(?=0)).(?:(?=1(?<1>){58044})|(?=0)).(?:(?=1(?<1>){16062})|(?=0)).(?:(?=1(?<1>){39616})|(?=0)).(?:(?=1(?<1>){31425})|(?=0)).(?:(?=1(?<1>){94404})|(?=0)).(?:(?=1(?<1>){86848})|(?=0)).(?:(?=1(?<1>){16589})|(?=0)).(?:(?=1(?<1>){195280})|(?=0)).(?:(?=1(?<1>){199377})|(?=0)).(?:(?=1(?<1>){43731})|(?=0)).(?:(?=1(?<1>){67534})|(?=0)).(?:(?=1(?<1>){106198})|(?=0)).(?:(?=1(?<1>){54999})|(?=0)).(?:(?=1(?<1>){52952})|(?=0)).(?:(?=1(?<1>){125828})|(?=0)).(?:(?=1(?<1>){169691})|(?=0)).(?:(?=1(?<1>){184542})|(?=0)).(?:(?=1(?<1>){177888})|(?=0)).(?:(?=1(?<1>){43233})|(?=0)).(?:(?=1(?<1>){127203})|(?=0)).(?:(?=1(?<1>){116518})|(?=0)).(?:(?=1(?<1>){117990})|(?=0)).(?:(?=1(?<1>){67815})|(?=0)).(?:(?=1(?<1>){62202})|(?=0)).(?:(?=1(?<1>){165611})|(?=0)).(?:(?=1(?<1>){197356})|(?=0)).(?:(?=1(?<1>){29933})|(?=0)).(?:(?=1(?<1>){90862})|(?=0)).(?:(?=1(?<1>){90863})|(?=0)).(?:(?=1(?<1>){149232})|(?=0)).(?:(?=1(?<1>){61681})|(?=0)).(?:(?=1(?<1>){137970})|(?=0)).(?:(?=1(?<1>){90357})|(?=0)).(?:(?=1(?<1>){47351})|(?=0)).(?:(?=1(?<1>){172509})|(?=0)).(?:(?=1(?<1>){78293})|(?=0)).(?:(?=1(?<1>){66303})|(?=0)).(?:(?=1(?<1>){66262})|(?=0)).(?:(?=1(?<1>){158471})|(?=0)).(?:(?=1(?<1>){5676})|(?=0)).(?:(?=1(?<1>){127242})|(?=0)).(?:(?=1(?<1>){51979})|(?=0)).(?:(?=1(?<1>){162060})|(?=0)).(?:(?=1(?<1>){27405})|(?=0)).(?:(?=1(?<1>){153874})|(?=0)).(?:(?=1(?<1>){150291})|(?=0)).(?:(?=1(?<1>){1814})|(?=0)).(?:(?=1(?<1>){193815})|(?=0)).(?:(?=1(?<1>){82200})|(?=0)).(?:(?=1(?<1>){59161})|(?=0)).(?:(?=1(?<1>){78620})|(?=0)).(?:(?=1(?<1>){123678})|(?=0)).(?:(?=1(?<1>){147232})|(?=0)).(?:(?=1(?<1>){71457})|(?=0)).(?:(?=1(?<1>){118562})|(?=0)).(?:(?=1(?<1>){129830})|(?=0)).(?:(?=1(?<1>){161841})|(?=0)).(?:(?=1(?<1>){60295})|(?=0)).(?:(?=1(?<1>){165426})|(?=0)).(?:(?=1(?<1>){107485})|(?=0)).(?:(?=1(?<1>){171828})|(?=0)).(?:(?=1(?<1>){166200})|(?=0)).(?:(?=1(?<1>){35124})|(?=0)).(?:(?=1(?<1>){160573})|(?=0)).(?:(?=1(?<1>){7486})|(?=0)).(?:(?=1(?<1>){169279})|(?=0)).(?:(?=1(?<1>){151360})|(?=0)).(?:(?=1(?<1>){6978})|(?=0)).(?:(?=1(?<1>){136003})|(?=0)).(?:(?=1(?<1>){56133})|(?=0)).(?:(?=1(?<1>){8520})|(?=0)).(?:(?=1(?<1>){87436})|(?=0)).(?:(?=1(?<1>){57162})|(?=0)).(?:(?=1(?<1>){197965})|(?=0)).(?:(?=1(?<1>){145230})|(?=0)).(?:(?=1(?<1>){95459})|(?=0)).(?:(?=1(?<1>){180564})|(?=0)).(?:(?=1(?<1>){157850})|(?=0)).(?:(?=1(?<1>){109399})|(?=0)).(?:(?=1(?<1>){191832})|(?=0)).(?:(?=1(?<1>){110223})|(?=0)).(?:(?=1(?<1>){75102})|(?=0)).(?:(?=1(?<1>){140639})|(?=0)).(?:(?=1(?<1>){49504})|(?=0)).(?:(?=1(?<1>){197987})|(?=0)).(?:(?=1(?<1>){52744})|(?=0)).(?:(?=1(?<1>){96615})|(?=0)).(?:(?=1(?<1>){13672})|(?=0)).(?:(?=1(?<1>){73068})|(?=0)).(?:(?=1(?<1>){104814})|(?=0)).(?:(?=1(?<1>){66929})|(?=0)).(?:(?=1(?<1>){23410})|(?=0)).(?:(?=1(?<1>){122686})|(?=0)).(?:(?=1(?<1>){44918})|(?=0)).(?:(?=1(?<1>){101752})|(?=0)).(?:(?=1(?<1>){3961})|(?=0)).(?:(?=1(?<1>){31807})|(?=0)).(?:(?=1(?<1>){54933})|(?=0)).(?:(?=1(?<1>){140096})|(?=0)).(?:(?=1(?<1>){49026})|(?=0)).(?:(?=1(?<1>){5507})|(?=0)).(?:(?=1(?<1>){96132})|(?=0)).(?:(?=1(?<1>){167303})|(?=0)).(?:(?=1(?<1>){57877})|(?=0)).(?:(?=1(?<1>){88461})|(?=0)).(?:(?=1(?<1>){111853})|(?=0)).(?:(?=1(?<1>){126531})|(?=0)).(?:(?=1(?<1>){110998})|(?=0)).(?:(?=1(?<1>){7575})|(?=0)).(?:(?=1(?<1>){7064})|(?=0)).(?:(?=1(?<1>){59289})|(?=0)).(?:(?=1(?<1>){122203})|(?=0)).(?:(?=1(?<1>){175005})|(?=0)).(?:(?=1(?<1>){28025})|(?=0)).(?:(?=1(?<1>){49057})|(?=0)).(?:(?=1(?<1>){6373})|(?=0)).(?:(?=1(?<1>){50084})|(?=0)).(?:(?=1(?<1>){70565})|(?=0)).(?:(?=1(?<1>){75178})|(?=0)).(?:(?=1(?<1>){142763})|(?=0)).(?:(?=1(?<1>){56237})|(?=0)).(?:(?=1(?<1>){32176})|(?=0)).(?:(?=1(?<1>){113073})|(?=0)).(?:(?=1(?<1>){149939})|(?=0)).(?:(?=1(?<1>){16308})|(?=0)).(?:(?=1(?<1>){12725})|(?=0)).(?:(?=1(?<1>){75190})|(?=0)).(?:(?=1(?<1>){54711})|(?=0)).(?:(?=1(?<1>){180664})|(?=0)).(?:(?=1(?<1>){68540})|(?=0)).(?:(?=1(?<1>){93117})|(?=0)).(?:(?=1(?<1>){161781})|(?=0)).(?:(?=1(?<1>){15808})|(?=0)).(?:(?=1(?<1>){130814})|(?=0)).(?:(?=1(?<1>){162379})|(?=0)).(?:(?=1(?<1>){80836})|(?=0)).(?:(?=1(?<1>){149943})|(?=0)).(?:(?=1(?<1>){16841})|(?=0)).(?:(?=1(?<1>){149452})|(?=0)).(?:(?=1(?<1>){182733})|(?=0)).(?:(?=1(?<1>){56270})|(?=0)).(?:(?=1(?<1>){163792})|(?=0)).(?:(?=1(?<1>){34770})|(?=0)).(?:(?=1(?<1>){101843})|(?=0)).(?:(?=1(?<1>){199124})|(?=0)).(?:(?=1(?<1>){129493})|(?=0)).(?:(?=1(?<1>){43990})|(?=0)).(?:(?=1(?<1>){113112})|(?=0)).(?:(?=1(?<1>){71129})|(?=0)).(?:(?=1(?<1>){61402})|(?=0)).(?:(?=1(?<1>){145852})|(?=0)).(?:(?=1(?<1>){98781})|(?=0)).(?:(?=1(?<1>){141790})|(?=0)).(?:(?=1(?<1>){163235})|(?=0)).(?:(?=1(?<1>){110566})|(?=0)).(?:(?=1(?<1>){117737})|(?=0)).(?:(?=1(?<1>){67050})|(?=0)).(?:(?=1(?<1>){68075})|(?=0)).(?:(?=1(?<1>){124047})|(?=0)).(?:(?=1(?<1>){181587})|(?=0)).(?:(?=1(?<1>){125429})|(?=0)).(?:(?=1(?<1>){112118})|(?=0)).(?:(?=1(?<1>){196088})|(?=0)).(?:(?=1(?<1>){25082})|(?=0)).(?:(?=1(?<1>){178684})|(?=0)).(?:(?=1(?<1>){13822})|(?=0)).(?<-1>){10094986}(?(1)(?!))$

We just can't have enough NP-complete problems! Here's the expanded version:
^
(?:(?=1(?<1>){5632})|(?=0)).
(?:(?=1(?<1>){79361})|(?=0)).
(?:(?=1(?<1>){188421})|(?=0)).
(?:(?=1(?<1>){164870})|(?=0)).
(?:(?=1(?<1>){63496})|(?=0)).
(?:(?=1(?<1>){116233})|(?=0)).
(?:(?=1(?<1>){112138})|(?=0)).
(?:(?=1(?<1>){47447})|(?=0)).
(?:(?=1(?<1>){85005})|(?=0)).
(?:(?=1(?<1>){17936})|(?=0)).
(?:(?=1(?<1>){108053})|(?=0)).
(?:(?=1(?<1>){88599})|(?=0)).
(?:(?=1(?<1>){91672})|(?=0)).
(?:(?=1(?<1>){178716})|(?=0)).
(?:(?=1(?<1>){199710})|(?=0)).
(?:(?=1(?<1>){166661})|(?=0)).
(?:(?=1(?<1>){190496})|(?=0)).
(?:(?=1(?<1>){184494})|(?=0)).
(?:(?=1(?<1>){199203})|(?=0)).
(?:(?=1(?<1>){116778})|(?=0)).
(?:(?=1(?<1>){78891})|(?=0)).
(?:(?=1(?<1>){192556})|(?=0)).
(?:(?=1(?<1>){24995})|(?=0)).
(?:(?=1(?<1>){1071})|(?=0)).
(?:(?=1(?<1>){192561})|(?=0)).
(?:(?=1(?<1>){108082})|(?=0)).
(?:(?=1(?<1>){1593})|(?=0)).
(?:(?=1(?<1>){26967})|(?=0)).
(?:(?=1(?<1>){197983})|(?=0)).
(?:(?=1(?<1>){97034})|(?=0)).
(?:(?=1(?<1>){86965})|(?=0)).
(?:(?=1(?<1>){60480})|(?=0)).
(?:(?=1(?<1>){149571})|(?=0)).
(?:(?=1(?<1>){100932})|(?=0)).
(?:(?=1(?<1>){40519})|(?=0)).
(?:(?=1(?<1>){173492})|(?=0)).
(?:(?=1(?<1>){80972})|(?=0)).
(?:(?=1(?<1>){115790})|(?=0)).
(?:(?=1(?<1>){29265})|(?=0)).
(?:(?=1(?<1>){91730})|(?=0)).
(?:(?=1(?<1>){173140})|(?=0)).
(?:(?=1(?<1>){52821})|(?=0)).
(?:(?=1(?<1>){176726})|(?=0)).
(?:(?=1(?<1>){170211})|(?=0)).
(?:(?=1(?<1>){150105})|(?=0)).
(?:(?=1(?<1>){23131})|(?=0)).
(?:(?=1(?<1>){81503})|(?=0)).
(?:(?=1(?<1>){77412})|(?=0)).
(?:(?=1(?<1>){106086})|(?=0)).
(?:(?=1(?<1>){4284})|(?=0)).
(?:(?=1(?<1>){142610})|(?=0)).
(?:(?=1(?<1>){167534})|(?=0)).
(?:(?=1(?<1>){190577})|(?=0)).
(?:(?=1(?<1>){147731})|(?=0)).
(?:(?=1(?<1>){133748})|(?=0)).
(?:(?=1(?<1>){194750})|(?=0)).
(?:(?=1(?<1>){49257})|(?=0)).
(?:(?=1(?<1>){49274})|(?=0)).
(?:(?=1(?<1>){120767})|(?=0)).
(?:(?=1(?<1>){172668})|(?=0)).
(?:(?=1(?<1>){24703})|(?=0)).
(?:(?=1(?<1>){108160})|(?=0)).
(?:(?=1(?<1>){60546})|(?=0)).
(?:(?=1(?<1>){56963})|(?=0)).
(?:(?=1(?<1>){30340})|(?=0)).
(?:(?=1(?<1>){95368})|(?=0)).
(?:(?=1(?<1>){59530})|(?=0)).
(?:(?=1(?<1>){53388})|(?=0)).
(?:(?=1(?<1>){14477})|(?=0)).
(?:(?=1(?<1>){28302})|(?=0)).
(?:(?=1(?<1>){182927})|(?=0)).
(?:(?=1(?<1>){59024})|(?=0)).
(?:(?=1(?<1>){146200})|(?=0)).
(?:(?=1(?<1>){153746})|(?=0)).
(?:(?=1(?<1>){39571})|(?=0)).
(?:(?=1(?<1>){134293})|(?=0)).
(?:(?=1(?<1>){158362})|(?=0)).
(?:(?=1(?<1>){170139})|(?=0)).
(?:(?=1(?<1>){182940})|(?=0)).
(?:(?=1(?<1>){7327})|(?=0)).
(?:(?=1(?<1>){143525})|(?=0)).
(?:(?=1(?<1>){119464})|(?=0)).
(?:(?=1(?<1>){82090})|(?=0)).
(?:(?=1(?<1>){170667})|(?=0)).
(?:(?=1(?<1>){49522})|(?=0)).
(?:(?=1(?<1>){69806})|(?=0)).
(?:(?=1(?<1>){15535})|(?=0)).
(?:(?=1(?<1>){16049})|(?=0)).
(?:(?=1(?<1>){163358})|(?=0)).
(?:(?=1(?<1>){181876})|(?=0)).
(?:(?=1(?<1>){58044})|(?=0)).
(?:(?=1(?<1>){16062})|(?=0)).
(?:(?=1(?<1>){39616})|(?=0)).
(?:(?=1(?<1>){31425})|(?=0)).
(?:(?=1(?<1>){94404})|(?=0)).
(?:(?=1(?<1>){86848})|(?=0)).
(?:(?=1(?<1>){16589})|(?=0)).
(?:(?=1(?<1>){195280})|(?=0)).
(?:(?=1(?<1>){199377})|(?=0)).
(?:(?=1(?<1>){43731})|(?=0)).
(?:(?=1(?<1>){67534})|(?=0)).
(?:(?=1(?<1>){106198})|(?=0)).
(?:(?=1(?<1>){54999})|(?=0)).
(?:(?=1(?<1>){52952})|(?=0)).
(?:(?=1(?<1>){125828})|(?=0)).
(?:(?=1(?<1>){169691})|(?=0)).
(?:(?=1(?<1>){184542})|(?=0)).
(?:(?=1(?<1>){177888})|(?=0)).
(?:(?=1(?<1>){43233})|(?=0)).
(?:(?=1(?<1>){127203})|(?=0)).
(?:(?=1(?<1>){116518})|(?=0)).
(?:(?=1(?<1>){117990})|(?=0)).
(?:(?=1(?<1>){67815})|(?=0)).
(?:(?=1(?<1>){62202})|(?=0)).
(?:(?=1(?<1>){165611})|(?=0)).
(?:(?=1(?<1>){197356})|(?=0)).
(?:(?=1(?<1>){29933})|(?=0)).
(?:(?=1(?<1>){90862})|(?=0)).
(?:(?=1(?<1>){90863})|(?=0)).
(?:(?=1(?<1>){149232})|(?=0)).
(?:(?=1(?<1>){61681})|(?=0)).
(?:(?=1(?<1>){137970})|(?=0)).
(?:(?=1(?<1>){90357})|(?=0)).
(?:(?=1(?<1>){47351})|(?=0)).
(?:(?=1(?<1>){172509})|(?=0)).
(?:(?=1(?<1>){78293})|(?=0)).
(?:(?=1(?<1>){66303})|(?=0)).
(?:(?=1(?<1>){66262})|(?=0)).
(?:(?=1(?<1>){158471})|(?=0)).
(?:(?=1(?<1>){5676})|(?=0)).
(?:(?=1(?<1>){127242})|(?=0)).
(?:(?=1(?<1>){51979})|(?=0)).
(?:(?=1(?<1>){162060})|(?=0)).
(?:(?=1(?<1>){27405})|(?=0)).
(?:(?=1(?<1>){153874})|(?=0)).
(?:(?=1(?<1>){150291})|(?=0)).
(?:(?=1(?<1>){1814})|(?=0)).
(?:(?=1(?<1>){193815})|(?=0)).
(?:(?=1(?<1>){82200})|(?=0)).
(?:(?=1(?<1>){59161})|(?=0)).
(?:(?=1(?<1>){78620})|(?=0)).
(?:(?=1(?<1>){123678})|(?=0)).
(?:(?=1(?<1>){147232})|(?=0)).
(?:(?=1(?<1>){71457})|(?=0)).
(?:(?=1(?<1>){118562})|(?=0)).
(?:(?=1(?<1>){129830})|(?=0)).
(?:(?=1(?<1>){161841})|(?=0)).
(?:(?=1(?<1>){60295})|(?=0)).
(?:(?=1(?<1>){165426})|(?=0)).
(?:(?=1(?<1>){107485})|(?=0)).
(?:(?=1(?<1>){171828})|(?=0)).
(?:(?=1(?<1>){166200})|(?=0)).
(?:(?=1(?<1>){35124})|(?=0)).
(?:(?=1(?<1>){160573})|(?=0)).
(?:(?=1(?<1>){7486})|(?=0)).
(?:(?=1(?<1>){169279})|(?=0)).
(?:(?=1(?<1>){151360})|(?=0)).
(?:(?=1(?<1>){6978})|(?=0)).
(?:(?=1(?<1>){136003})|(?=0)).
(?:(?=1(?<1>){56133})|(?=0)).
(?:(?=1(?<1>){8520})|(?=0)).
(?:(?=1(?<1>){87436})|(?=0)).
(?:(?=1(?<1>){57162})|(?=0)).
(?:(?=1(?<1>){197965})|(?=0)).
(?:(?=1(?<1>){145230})|(?=0)).
(?:(?=1(?<1>){95459})|(?=0)).
(?:(?=1(?<1>){180564})|(?=0)).
(?:(?=1(?<1>){157850})|(?=0)).
(?:(?=1(?<1>){109399})|(?=0)).
(?:(?=1(?<1>){191832})|(?=0)).
(?:(?=1(?<1>){110223})|(?=0)).
(?:(?=1(?<1>){75102})|(?=0)).
(?:(?=1(?<1>){140639})|(?=0)).
(?:(?=1(?<1>){49504})|(?=0)).
(?:(?=1(?<1>){197987})|(?=0)).
(?:(?=1(?<1>){52744})|(?=0)).
(?:(?=1(?<1>){96615})|(?=0)).
(?:(?=1(?<1>){13672})|(?=0)).
(?:(?=1(?<1>){73068})|(?=0)).
(?:(?=1(?<1>){104814})|(?=0)).
(?:(?=1(?<1>){66929})|(?=0)).
(?:(?=1(?<1>){23410})|(?=0)).
(?:(?=1(?<1>){122686})|(?=0)).
(?:(?=1(?<1>){44918})|(?=0)).
(?:(?=1(?<1>){101752})|(?=0)).
(?:(?=1(?<1>){3961})|(?=0)).
(?:(?=1(?<1>){31807})|(?=0)).
(?:(?=1(?<1>){54933})|(?=0)).
(?:(?=1(?<1>){140096})|(?=0)).
(?:(?=1(?<1>){49026})|(?=0)).
(?:(?=1(?<1>){5507})|(?=0)).
(?:(?=1(?<1>){96132})|(?=0)).
(?:(?=1(?<1>){167303})|(?=0)).
(?:(?=1(?<1>){57877})|(?=0)).
(?:(?=1(?<1>){88461})|(?=0)).
(?:(?=1(?<1>){111853})|(?=0)).
(?:(?=1(?<1>){126531})|(?=0)).
(?:(?=1(?<1>){110998})|(?=0)).
(?:(?=1(?<1>){7575})|(?=0)).
(?:(?=1(?<1>){7064})|(?=0)).
(?:(?=1(?<1>){59289})|(?=0)).
(?:(?=1(?<1>){122203})|(?=0)).
(?:(?=1(?<1>){175005})|(?=0)).
(?:(?=1(?<1>){28025})|(?=0)).
(?:(?=1(?<1>){49057})|(?=0)).
(?:(?=1(?<1>){6373})|(?=0)).
(?:(?=1(?<1>){50084})|(?=0)).
(?:(?=1(?<1>){70565})|(?=0)).
(?:(?=1(?<1>){75178})|(?=0)).
(?:(?=1(?<1>){142763})|(?=0)).
(?:(?=1(?<1>){56237})|(?=0)).
(?:(?=1(?<1>){32176})|(?=0)).
(?:(?=1(?<1>){113073})|(?=0)).
(?:(?=1(?<1>){149939})|(?=0)).
(?:(?=1(?<1>){16308})|(?=0)).
(?:(?=1(?<1>){12725})|(?=0)).
(?:(?=1(?<1>){75190})|(?=0)).
(?:(?=1(?<1>){54711})|(?=0)).
(?:(?=1(?<1>){180664})|(?=0)).
(?:(?=1(?<1>){68540})|(?=0)).
(?:(?=1(?<1>){93117})|(?=0)).
(?:(?=1(?<1>){161781})|(?=0)).
(?:(?=1(?<1>){15808})|(?=0)).
(?:(?=1(?<1>){130814})|(?=0)).
(?:(?=1(?<1>){162379})|(?=0)).
(?:(?=1(?<1>){80836})|(?=0)).
(?:(?=1(?<1>){149943})|(?=0)).
(?:(?=1(?<1>){16841})|(?=0)).
(?:(?=1(?<1>){149452})|(?=0)).
(?:(?=1(?<1>){182733})|(?=0)).
(?:(?=1(?<1>){56270})|(?=0)).
(?:(?=1(?<1>){163792})|(?=0)).
(?:(?=1(?<1>){34770})|(?=0)).
(?:(?=1(?<1>){101843})|(?=0)).
(?:(?=1(?<1>){199124})|(?=0)).
(?:(?=1(?<1>){129493})|(?=0)).
(?:(?=1(?<1>){43990})|(?=0)).
(?:(?=1(?<1>){113112})|(?=0)).
(?:(?=1(?<1>){71129})|(?=0)).
(?:(?=1(?<1>){61402})|(?=0)).
(?:(?=1(?<1>){145852})|(?=0)).
(?:(?=1(?<1>){98781})|(?=0)).
(?:(?=1(?<1>){141790})|(?=0)).
(?:(?=1(?<1>){163235})|(?=0)).
(?:(?=1(?<1>){110566})|(?=0)).
(?:(?=1(?<1>){117737})|(?=0)).
(?:(?=1(?<1>){67050})|(?=0)).
(?:(?=1(?<1>){68075})|(?=0)).
(?:(?=1(?<1>){124047})|(?=0)).
(?:(?=1(?<1>){181587})|(?=0)).
(?:(?=1(?<1>){125429})|(?=0)).
(?:(?=1(?<1>){112118})|(?=0)).
(?:(?=1(?<1>){196088})|(?=0)).
(?:(?=1(?<1>){25082})|(?=0)).
(?:(?=1(?<1>){178684})|(?=0)).
(?:(?=1(?<1>){13822})|(?=0)).
(?<-1>){10094986}
(?(1)(?!))
$

 Each (?:(?=1(?<1>){n})|(?=0)). row pushes n empty strings to group 1 if the digit 1 is found, and does nothing if a 0 is found. (?<-1>){10094986}(?(1)(?!)) then checks that the total number of empty strings in group 1 by the end is 10094986. Hence our goal is to find a subset of the numbers such that their total is 10094986. This is exactly the subset sum problem, which is a special case of the knapsack problem, and is NP-complete.

Tested on Regex Hero (Regex Storm times out for this one).

Match: 01111111111111111111111011001111111111011111111111111111111101111111111 11111111111111111111011111111000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000 (remove those spaces). Non-match: KnapsackAlgorithm. It is not easy to install Silverlight on my Ubuntu machine. But this worked on some other tester.

@user23013 Ah oops, I forgot that required Silverlight. But honestly though, either I'm unlucky or there's a lot of solutions, because that's a stupidly long chain of 0s at the end there. Then again I'll need to get over the 32-bit int barrier first, I think I have an idea...

I already had 700+ bit integer in my latest answer!

@user23013 And you're telling us to factorise it? So mean! :P

The integer to factorise is 1536 bit.

.NET flavour (52506 bytes)
Subset sum, deluxe edition.
Regex here, expanded version here, tested on RegExLib and Regex Hero

 Match:1000010001000000001101011000001101110101001010011101000101010011011101000001010101001000010010000111011101100101001101001111000111010101100000101000101010110001010101001100100001110010001101010101100010110011000000110110000000011111101000001000011111100010
 Mismatch: Huzzah for NP-complete regexes
 This regex is one giant subset sum problem, and uses 16 groups to store data. Each 1 in the string represents 16 10-bit numbers, which together represent a 160-bit integer. The last few lines of the regex carry the values in the groups so that groups 2-16 go up to 1023 (e.g. 1*1023 + 1024 becomes 2*1023 + 1), as otherwise we'd only be solving 16 simultaneous mini subset sum problems as opposed to one big one.

Congratulations on making it through the 72 hours! You may now lock your answer against cracking by revealing the key. Until you do, the answer can still be cracked.

Perl flavor, 97 [cracked]
I'm afraid this is going to be too easy due to the key length limit.
^([^,]+),(?!\1)([^,]+),(?!\1|\2,)([^,]+),(?!\1|(?:\2|\3),)([^,]+),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

If you think you figured the idea behind it, try the longer version (not part of the challenge):
^((?:[^,]{3})+),(?!\1)([^,]+),(?!\1|\2,)([^,]+),(?!\1|(?:\2|\3),)([^,]+),(?!\1|(?:\2|\3|\4),)([^,]+),(?!\1|(?:\2|\3|\4|\5),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6),)([^,]+),(?!\1|(?:\2|\3|\4|\5|\6|\7),)([^,]+),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$

Match: aaaaaaa,a,aa,aaa,aaaaaaa. Non-match: aaaabaaacaaadaaa.

Longer version: Match: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa,a,aa,(remove these chars)aaaa,aaaaaaa,aaaaaaaa,aaaaaaaaaaaaaa,aaaaaaaaaaaaaaaaaaaaaaaaaaaa,(remove these chars)aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa. Non-match: aaaabaaacaaadaaa

@user23013: The short version is correct! I meant for the capture groups to be at least two characters long, which would have made the key a little bit longer, but I forgot to change it :P The longer version is incorrect, though.

This site added some invisible special characters when I posted them. I think it is fixed now. (Without the (remove these characters).)

@user23013 Yeah, that's a match. I really didn't plan for it to be that easy :P

Arggg lost by 4 mins

Perl flavor, 109 [cracked]
The previous submission turned out easier than I intended. This one should be a little more challenging, though the short version is still very much brute-forcible.
^([^,]+),(?!\1)([^,]{2,}),(?!\1|\2+,)([^,]{2,}),(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

And a longer version, not part of the challenge:
^([^,]+),(?!\1)([^,]{2,}),(?!\1|\2+,)([^,]{2,}),(?!\1|(?:\2+|\3+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+|\6+),)([^,]{2,}),(?!\1|(?:\2+|\3+|\4+|\5+|\6+|\7+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$

EDIT: The above version turned out too simple as well.
Here's a final attempt to make this more challenging.
Perl flavor, 121 [cracked]
Short version:
^([^,]+),(?!\1)([^,]{2,}),(?=\2)(?!\1|\2+,)([^,]{2,}),(?=\3)(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)\1+$

Long version:
^([^,]+),(?!\1)([^,]{2,}),(?=\2)(?!\1|\2+,)([^,]{2,}),(?=\3)(?!\1|(?:\2+|\3+),)([^,]{2,}),(?=\4)(?!\1|(?:\2+|\3+|\4+),)([^,]{2,}),(?=\5)(?!\1|(?:\2+|\3+|\4+|\5+),)([^,]{2,}),(?=\6)(?!\1|(?:\2+|\3+|\4+|\5+|\6+),)([^,]{2,}),(?=\7)(?!\1|(?:\2+|\3+|\4+|\5+|\6+|\7+),)([^,]{2,}),(?=.\2+$)(?=.\3+$)(?=.\4+$)(?=.\5+$)(?=.\6+$)(?=.\7+$)(?=.\8+$)\1+$

Match: aaaaaaaaaaaaa,aaaa,aaa,aa,aaaaaaaaaaaaa. Non-match: aaaabaaacaaadaaa.

Longer: Match: http://regex101.com/r/dT2rX8/1 Non-match: aaaabaaacaaadaaa

@user23013 You're on a roll! It wasn't supposed to be that easy, but I overlooked a few things. I don't want to post a third submission, but I'll edit this one with what I hope is a "correct" version this time. Give it a shot if you feel like it.

Shorter: http://regex101.com/r/lO1kX7/1 aaaabaaacaaadaaa. Longer: http://regex101.com/r/fD3qB4/1 aaaabaaacaaadaaa.

@Ell Posting a third submission would not have been a problem. (And feel free to do so if you come up with something else.)

@user23013 You got it! Still shorter than what I had in mind but it's getting warmer.

Python, 145245 bytes [cracked]
Credit to sp3000 & COTO for the idea
Uncompressed Pastebin copy: http://pastebin.com/jtp82dY9
EDIT: I screwed up the regex generator and made most of my clauses invalid. Congratulations Wumpus for finding and exploiting it :) I've submitted a fixed version, so I'll explain how these submissions work after they are cracked or the time-limit expires.

Tested on http://www.pythonregex.com/.

I think you can call it 145245, you don't need the newline at the end.

@WumpusQ.Wumbley: thanks, removed the newline

Non-match: 1657114133410330066437310300651114626477107270715027765071217477765155062115727346312156431331022432571707004067437201014346506056771002007472602676067730610061613313533367043345632652200101037575653036745227714523510655101775154755604257220747261564732730 Match: YouMessedUpMostOfYourClausesOnlyMatch255Characters

Ahahahah, and that's why we should test things more carefully....

JS-Compatible RegEx - 70 bytes [cracked]
Auch, I'm bad at this. :P
[^a]|^(a{0,16}|(?:(?=((a{9,275})\1\2\3))\2)+(a?){6}|(a{3181}){902}a+)$

Resolves on virtually any string instantaneously. Tested on RegExr.

Yes. Uh... wait. When did you add the 256 character maximum? Was that there all the time?

No it wasn't, I added it 4 hours ago, see the second comment on the question. Sorry about the confusion.

Decided to undelete this since people might have fun cracking it. Readers should note that this submission is not to spec (the key is vastly longer than 256 chars), hence it won't count towards a cracking score. The key can be trivially described, however.

Match: aaaaaaaaaaaaaaaa -- Non-match: aaaaaaaaaaaaaaaaa

Sorry but: "Cracked submissions are eliminated from contention (provided they are not "safe"). They should not be edited or deleted. If an author wishes to submit a new regex, (s)he should do so in a separate answer." ;)

@Dennis - I set the upper bound on the a{0,17} by one too little when I edited the question. It's repaired now. My apologies for the error. Please reattempt.

@MartinBüttner: Fair enough. I'll submit a new answer.

Ruby flavor, 22 bytes [cracked]
^(?!(.+)\1)[\[\\\]]{256}$

Not so much obfuscated but a bit difficult to satisfy.

Match: [] followed by 254 ['s. No match: empty string

Sorry I didn't make both of my strings in the 16..256 range. Retry: Match: [] followed by 254 ['s. No match: 16 ['s

Oops, that did not work the way I thought it did. I'll post a modification as a separate answer to avoid messing with the score.

PCRE, 71 [cracked]
(((?!\3)(1++)\3){5,})(((1++)\3\6\2(?!\3)(?=1\6)){5,}1+)1\11

 There are 3 zero-width spaces (after both (1++)s and between the two big capture groups), and a right-to-left override before the last 4 characters so the last 4 characters are actually 1\11 (literal 1 then horizontal tab). Once you notice those all you have to do is put zero-width spaces at the right places (which I thought would be quite a challenge in itself).

In hindsight I should have used 1+ instead of 1++

Match: http://regex101.com/r/kH2oX7/1 Non-match: aaaabaaacaaadaaa. Standard loophole?

Damn! I thought this can at least hold on for a few hours.

I found it because it looks too impossible. And the online tester highlighted \11.

@user23013 Standard loophole because of Unicode? No, I'd say it's fine. This is an obfuscation contest, and I deliberately didn't disallow Unicode.

PHP and Javascript compatible (73 bytes + delimiters)[cracked]:
/^(((\xf4)\x65)\2(\x80)(\4\2))((\2(\x45\5)\x0A)(\2\x10\3))(\3(\\xf4\4)\2)$/

This was tested using the website http://regex101.com/ and http://www.gethifi.com/tools/regex .
Only matches one string. Have fun finding which!
To back up my answer, here is the last sentence of OP's comment, explaining the challenge:
In most cases, this means, either your regex accepts pretty much nothing except some non-obvious string, or it accepts pretty much everything except some non-obvious string. Cops and Robbers: Reverse Regex Golf
Please, don't crack it!

Well, @Dennis doesn't play by the rules and decided to break it.
Here is a printscreen of the matching string, using FireFox:

@MartinBüttner Actually, it's 75 :/ and I had the regex with some garbage on the same file, and checked the length of the whole file and not the selected length. I just updated with the right count. And all the chars are printable ascii chars.

Alright, I updated the count.

Match : \xf4\x65\xf4\x65\x80\x80\xf4\x65\xf4\x65\x45\x80\xf4\x65\x0A\xf4\x65\x10\xf4\xf4\\xf4\x80\xf4\x65 (JavaScript string with escapes) -- Non-match: RegExCopsandRobbers

Is it actually possible to enter that string in regex101? With the \x10 (Ctrl-P) in it?

@WumpusQ.Wumbley You can enter it into your browser's console as a string and copy the result into regex101.

@WumpusQ.Wumbley http://regex101.com/r/tE3vR4/1

@Dennis Goddamn! But I don't get one thing: why that cross char is matching, but well. Here is a link to the printscreen of the answer, taken from firefox: http://tinypic.com/r/wwnsz5/8

Ruby-flavored, 32 bytes [cracked]
^(?!.*((.).+)\1\2)[ah]{105}(?=!a*)

Match: aaaahaaaahhaaaahaaahhaaaahhahaaaahaaahhaaaahaahhaaaahhaahaaaahaahhaaaahaaahhaaaahahhaaaahhaaahaaaahahhaaa! copy at http://rubular.com/r/YPgdPbBB7U No match: heheheheheheheh!

ECMAScript flavor, 39 bytes [cracked :(]
^.(.)\\\^-\^\\.(.)\\\^-\^\\.(?=\1*$)\2$

My first regex, hopefully it's not too easy. You can test it at http://www.regexr.com/

Match: aa\^-^\aa\^-^\aa, Non-match: aa\^-^\aa\^-b\aa

JS-Compatible RegEx - 70 bytes [cracked]
[^a]|^(a{0,25}|(?:(?=((a{9,275})\1\2\3))\2)+(a?){6}|(a{3181}){902}a+)$

Resolves on virtually any string instantaneously. Tested on RegExr. Identical to the previous 70 byte submission except an error is fixed.
Broken for some reason. :(
Intended functionality:
[^a]                   # match any string containing anything except "a"s
 | or
^(
    a{0,25}            # match any string of 25 or fewer "a"s
 | or
    (?:                # block matches (or _should_ match) any string of "a"s with
                       # length n such that n ≢ {0,1,2,3,4,5,6} (mod x)
                       # for all x ∈ [9:275].  The 3 smallest n that satisfy this property
                       # are n = 7, n = 1,346,407 and n = 2,914,919.
                       # Strings of length < 26 are matched by the first alternate, and
                       # strings of length > 2,869,262 are matched by the third alternate,
                       # hence the sole key should be 1,346,407.

                       # Capture groups \1 and \2 are undefined and should be empty in
                       # the \1\2\3 sequence.
                       # The problem is with the lookahead. It seems to be making
                       # the parser treat a{9,275} as atomic in some cases and not in
                       # others ???
        (?=((a{9,275}) \1\2\3))\2
    )+
    (a?){6}
 | or
    (a{3181}){902}a+   # match any string of 2,869,263+ "a"s
)$

____< Today is not going well for me.

As in your previous submission, the key is longer than 256 bytes, yes?

Yes. It's identical, technically non-spec. Martin gave you credit for the previous one. The solution can be described trivially, so it seems to still be "in the spirit" of the limit, which (as I understand it) was so that the solutions could be expressed in a matter of a few characters.

Match: a repeated 556 times -- Non-match: a repeated 557 times

I suppose he gave me credit because I found a key that satisfies the spec.

sigh OK. It's obviously not functioning the way I expected it to. I added some things last minute that didn't appear to "break" it, but evidently I was wrong. I'll post an explanation of the intended functionality and perhaps somebody can figure out why it's not working.

Lookaheads are always atomic. As long as you're within the lookahead it backtracks, but once the lookahead is satisfied, the engine won't backtrack into it again.

That's what the regex reference said. But something like a 557 times can't possibly match without backtracking here, so I figured that FF's implementation of regex was nonstandard in that sense.

JavaScript, 78 bytes
^(([a-z])*[0-2]?[7-9]+[3-6]*^{5892}+^x?[A-Z]?[A-G]*)^{6Q}*^{2}+{\{\}}*{\[\]}+

authors: n̴̖̋h̷͉̃a̷̭̿h̸̡̅ẗ̵̨́d̷̰̀ĥ̷̳

authors: Αλεκος Ζαζόπουλος

all_licenses: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/3.0/