class Ideone {
	public static void main (String[] args) {
        String file =
                "other stuff\n" +
                ":59:Line with random data and length\n" +
                "RANDOM VALUE\n" +
                "TO BE\n" +
                "EXTRACTED\n" +
                ":71A:SHA\n" +
                "more stuff";
        String target = file.replaceAll("(?ms).*^:59:.*?\n(.*)^:71A:.*", "$1");
        System.out.println(target);
	}
}

Y2xhc3MgSWRlb25lIHsKCXB1YmxpYyBzdGF0aWMgdm9pZCBtYWluIChTdHJpbmdbXSBhcmdzKSB7CiAgICAgICAgU3RyaW5nIGZpbGUgPQogICAgICAgICAgICAgICAgIm90aGVyIHN0dWZmXG4iICsKICAgICAgICAgICAgICAgICI6NTk6TGluZSB3aXRoIHJhbmRvbSBkYXRhIGFuZCBsZW5ndGhcbiIgKwogICAgICAgICAgICAgICAgIlJBTkRPTSBWQUxVRVxuIiArCiAgICAgICAgICAgICAgICAiVE8gQkVcbiIgKwogICAgICAgICAgICAgICAgIkVYVFJBQ1RFRFxuIiArCiAgICAgICAgICAgICAgICAiOjcxQTpTSEFcbiIgKwogICAgICAgICAgICAgICAgIm1vcmUgc3R1ZmYiOwogICAgICAgIFN0cmluZyB0YXJnZXQgPSBmaWxlLnJlcGxhY2VBbGwoIig/bXMpLipeOjU5Oi4qP1xuKC4qKV46NzFBOi4qIiwgIiQxIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHRhcmdldCk7Cgl9Cn0=